1542 Бессонова

1. 1542. Реализация префиксного дерева для предиктивного ввода команд

Отчёт о выполнении курсовой работы по дисциплине
«Программирование и основы алгоритмизации»
Выполнил студент гр. КРБО-02-17
Бессонова А.В.

2. Постановка задачи

Вкратце:
Что-то про автодополнение для японцев
На ввод поступает от 1 до 105 японских слов (на латинице, до 15 символов) и
частота их встреч.
Затем даётся от 1 до 15000 «фраз»: начал слова, введённого пользователем.
Для каждой фразы нужно вывести список слов – автодополнений, не более 10. Эти
слова должны:
1. начинаться на фразу;
2. быть отсортированы по частоте встреч;
3. для одинаковых частот – сортировка лексикографически, по алфавиту.

3. решение

А так же его попытки

4. Первая мысль

Дерево
Ввод
корень
konojo 10
Идеальным вариантом для решения
этой задачи показалось
использование префиксного дерева

5. Первая мысль

Дерево
Ввод
корень
konojo 10
k
Идеальным вариантом для решения
этой задачи показалось
использование префиксного дерева

6. Первая мысль

Дерево
Ввод
корень
konojo 10
k
o
Идеальным вариантом для решения
этой задачи показалось
использование префиксного дерева

7. Первая мысль

Дерево
Ввод
корень
konojo 10
k
o
n
Идеальным вариантом для решения
этой задачи показалось
использование префиксного дерева

8. Первая мысль

Дерево
Ввод
корень
konojo 10
k
o
n
o
Идеальным вариантом для решения
этой задачи показалось
использование префиксного дерева

9. Первая мысль

Дерево
Ввод
корень
konojo 10
k
o
n
o
j
Идеальным вариантом для решения
этой задачи показалось
использование префиксного дерева

10. Первая мысль

Дерево
Ввод
корень
konojo 10
k
o
n
o
j
o
Идеальным вариантом для решения
этой задачи показалось
использование префиксного дерева

11. Первая мысль

Дерево
Ввод
корень
konojo 10
k
o
n
o
j
o
konojo
10
Идеальным вариантом для решения
этой задачи показалось
использование префиксного дерева

12. Первая мысль

Дерево
Ввод
корень
konojo 10
konma 5
k
o
n
o
j
o
konojo
10
Идеальным вариантом для решения
этой задачи показалось
использование префиксного дерева

13. Первая мысль

Дерево
Ввод
корень
konojo 10
konma 5
k
o
n
o
j
o
konojo
10
Идеальным вариантом для решения
этой задачи показалось
использование префиксного дерева

14. Первая мысль

Дерево
Ввод
корень
konojo 10
konma 5
k
o
n
o
j
o
konojo
10
Идеальным вариантом для решения
этой задачи показалось
использование префиксного дерева

15. Первая мысль

Дерево
Ввод
корень
konojo 10
konma 5
k
o
n
o
j
o
konojo
10
Идеальным вариантом для решения
этой задачи показалось
использование префиксного дерева

16. Первая мысль

Дерево
Ввод
корень
konojo 10
konma 5
k
Идеальным вариантом для решения
этой задачи показалось
использование префиксного дерева
o
n
o
j
o
konojo
10
m

17. Первая мысль

Дерево
Ввод
корень
konojo 10
konma 5
k
Идеальным вариантом для решения
этой задачи показалось
использование префиксного дерева
o
n
o
m
j
a
o
konojo
10

18. Первая мысль

Дерево
Ввод
корень
konojo 10
konma 5
k
Идеальным вариантом для решения
этой задачи показалось
использование префиксного дерева
o
n
o
m
j
a
o
konma
5
konojo
10

19. Первая мысль

Дерево
Поиск и вывод
фраза
корень
kon
k
Идеальным вариантом для решения
этой задачи показалось
использование префиксного дерева
o
n
o
m
j
a
o
konma
5
konojo
10
результат

20. Первая мысль

Дерево
Поиск и вывод
фраза
корень
kon
k
Идеальным вариантом для решения
этой задачи показалось
использование префиксного дерева
o
n
o
m
j
a
o
konma
5
konojo
10
результат

21. Первая мысль

Дерево
Поиск и вывод
фраза
корень
kon
k
Идеальным вариантом для решения
этой задачи показалось
использование префиксного дерева
o
n
o
m
j
a
o
konma
5
konojo
10
результат

22. Первая мысль

Дерево
Поиск и вывод
фраза
корень
kon
k
Идеальным вариантом для решения
этой задачи показалось
использование префиксного дерева
o
n
o
m
j
a
o
konma
5
konojo
10
результат

23. Первая мысль

Дерево
Поиск и вывод
фраза
корень
kon
k
Идеальным вариантом для решения
этой задачи показалось
использование префиксного дерева
o
n
o
m
j
a
o
konma
5
konojo
10
результат

24. Первая мысль

Дерево
Поиск и вывод
фраза
корень
kon
k
Идеальным вариантом для решения
этой задачи показалось
использование префиксного дерева
o
n
o
m
j
a
o
konma
5
konojo
10
результат

25. Первая мысль

Дерево
Поиск и вывод
предварительный
результат
корень
k
konma
5
o
n
o
m
j
a
o
konma
5
konojo
10
фраза
результат
kon
Идеальным вариантом для решения
этой задачи показалось
использование префиксного дерева

26. Первая мысль

Дерево
Поиск и вывод
предварительный
результат
корень
k
konma
5
o
n
o
m
j
a
o
konma
5
konojo
10
фраза
результат
kon
Идеальным вариантом для решения
этой задачи показалось
использование префиксного дерева

27. Первая мысль

Дерево
Поиск и вывод
предварительный
результат
корень
k
konma
5
o
n
o
m
j
a
o
konma
5
konojo
10
фраза
результат
kon
Идеальным вариантом для решения
этой задачи показалось
использование префиксного дерева

28. Первая мысль

Дерево
Поиск и вывод
предварительный
результат
корень
k
konma
5
o
n
o
m
j
a
o
konma
5
konojo
10
фраза
результат
kon
Идеальным вариантом для решения
этой задачи показалось
использование префиксного дерева

29. Первая мысль

Дерево
Поиск и вывод
предварительный
результат
корень
k
konma
5
o
konojo
10
n
o
m
j
a
o
konma
5
konojo
10
фраза
результат
kon
Идеальным вариантом для решения
этой задачи показалось
использование префиксного дерева

30. Первая мысль

Дерево
Поиск и вывод
фраза
корень
kon
k
Идеальным вариантом для решения
этой задачи показалось
использование префиксного дерева
o
n
o
m
j
a
o
konma
5
konojo
10
результат

31. Первая мысль

Дерево
Поиск и вывод
корень
k
результат
kon
konojo
konma
Идеальным вариантом для решения
этой задачи показалось
использование префиксного дерева
o
n
o
m
j
a
o
konma
5
konojo
10
фраза

32. проблема

Слишком медленно
В целом, это решение работало, но
не проходило по временному
ограничению (2 секунды)

33. Вторая мысль

Кэширование
Сохраняем результаты для каждой введённой фразы
Если фраза есть в сохранённых, выводим сохранённые
результаты
А что, если нам посылают много
одинаковых фраз? Мы будем для
каждой искать и сортировать
результат, что долго.

34. проблема

Слишком прожорливо
Тест, упиравшийся во временной
лимит, прошёл, но на одном из
следующих решение вышло за
лимит памяти.

35. третья мысль

Кэш не должен съедать слишком
много, скорее всего проблема в
дереве. А как его можно
оптимизировать?

36. третья мысль

Зачем хранить в словаре значения, которые никто не
спросит?
Зачем сортировать результат, если можно его хранить
предварительно отсортированным?
Сегодня в завтрашний день могут
смотреть не только лишь все,
а мы в будущее – можем

37. третья мысль

Дерево
корень
Ввод
11
haiwee 15
haiweebasu 4
haichijin 1
hautsuu 15
hurannneru 3
huruni 8
hotto 125
horumon 15
howaito 23
hurasuko 34
hukku 1
2
h
k
Сегодня в завтрашний день могут
смотреть не только лишь все,
а мы в будущее – можем

38. третья мысль

Дерево
корень
h
Ввод
11
haiwee 15
haiweebasu 4
haichijin 1
hautsuu 15
hurannneru 3
huruni 8
hotto 125
horumon 15
howaito 23
hurasuko 34
hukku 1
2
h
k
Сегодня в завтрашний день могут
смотреть не только лишь все,
а мы в будущее – можем

39. третья мысль

Дерево
корень
k
h
Ввод
11
haiwee 15
haiweebasu 4
haichijin 1
hautsuu 15
hurannneru 3
huruni 8
hotto 125
horumon 15
howaito 23
hurasuko 34
hukku 1
2
h
k
Сегодня в завтрашний день могут
смотреть не только лишь все,
а мы в будущее – можем

40. третья мысль

Дерево
корень
k
h
предсказания
1. haiwee 15
Ввод
11
haiwee 15
haiweebasu 4
haichijin 1
hautsuu 15
hurannneru 3
huruni 8
hotto 125
horumon 15
howaito 23
hurasuko 34
hukku 1
2
h
k
Сегодня в завтрашний день могут
смотреть не только лишь все,
а мы в будущее – можем

41. третья мысль

Дерево
корень
k
h
предсказания
1. haiwee 15
2. haiweebasu 4
Ввод
11
haiwee 15
haiweebasu 4
haichijin 1
hautsuu 15
hurannneru 3
huruni 8
hotto 125
horumon 15
howaito 23
hurasuko 34
hukku 1
2
h
k
Сегодня в завтрашний день могут
смотреть не только лишь все,
а мы в будущее – можем

42. третья мысль

Дерево
корень
k
h
предсказания
1. haiwee 15
2. haiweebasu 4
3. haichijin 1
Ввод
11
haiwee 15
haiweebasu 4
haichijin 1
hautsuu 15
hurannneru 3
huruni 8
hotto 125
horumon 15
howaito 23
hurasuko 34
hukku 1
2
h
k
Сегодня в завтрашний день могут
смотреть не только лишь все,
а мы в будущее – можем

43. третья мысль

Дерево
корень
k
h
предсказания
1. haiwee 15
2. hautsuu 15
3. haiweebasu 4
4. haichijin 1
Ввод
11
haiwee 15
haiweebasu 4
haichijin 1
hautsuu 15
hurannneru 3
huruni 8
hotto 125
horumon 15
howaito 23
hurasuko 34
hukku 1
2
h
k
Сегодня в завтрашний день могут
смотреть не только лишь все,
а мы в будущее – можем

44. третья мысль

Дерево
корень
k
h
предсказания
1. haiwee 15
2. hautsuu 15
3. haiweebasu 4
4. hurannneru 3
5. haichijin 1
Ввод
11
haiwee 15
haiweebasu 4
haichijin 1
hautsuu 15
hurannneru 3
huruni 8
hotto 125
horumon 15
howaito 23
hurasuko 34
hukku 1
2
h
k
Сегодня в завтрашний день могут
смотреть не только лишь все,
а мы в будущее – можем

45. третья мысль

Дерево
корень
k
h
предсказания
1. haiwee 15
2. hautsuu 15
3. huruni 8
4. haiweebasu 4
5. hurannneru 3
6. haichijin 1
Ввод
11
haiwee 15
haiweebasu 4
haichijin 1
hautsuu 15
hurannneru 3
huruni 8
hotto 125
horumon 15
howaito 23
hurasuko 34
hukku 1
2
h
k
Сегодня в завтрашний день могут
смотреть не только лишь все,
а мы в будущее – можем

46. третья мысль

Дерево
корень
k
h
предсказания
1. hotto 125
2. haiwee 15
3. hautsuu 15
4. huruni 8
5. haiweebasu 4
6. hurannneru 3
7. haichijin 1
Ввод
11
haiwee 15
haiweebasu 4
haichijin 1
hautsuu 15
hurannneru 3
huruni 8
hotto 125
horumon 15
howaito 23
hurasuko 34
hukku 1
2
h
k
Сегодня в завтрашний день могут
смотреть не только лишь все,
а мы в будущее – можем

47. третья мысль

Дерево
корень
k
h
предсказания
1. hotto 125
2. haiwee 15
3. hautsuu 15
4. horumon 15
5. huruni 8
6. haiweebasu 4
7. hurannneru 3
8. haichijin 1
Ввод
11
haiwee 15
haiweebasu 4
haichijin 1
hautsuu 15
hurannneru 3
huruni 8
hotto 125
horumon 15
howaito 23
hurasuko 34
hukku 1
2
h
k
Сегодня в завтрашний день могут
смотреть не только лишь все,
а мы в будущее – можем

48. третья мысль

Дерево
корень
k
h
предсказания
1. hotto 125
2. howaito 23
3. haiwee 15
4. hautsuu 15
5. horumon 15
6. huruni 8
7. haiweebasu 4
8. hurannneru 3
9. haichijin 1
Ввод
11
haiwee 15
haiweebasu 4
haichijin 1
hautsuu 15
hurannneru 3
huruni 8
hotto 125
horumon 15
howaito 23
hurasuko 34
hukku 1
2
h
k
Сегодня в завтрашний день могут
смотреть не только лишь все,
а мы в будущее – можем

49. третья мысль

Дерево
корень
k
h
предсказания
1. hotto 125
2. hurasuko 34
3. howaito 23
4. haiwee 15
5. hautsuu 15
6. horumon 15
7. huruni 8
8. haiweebasu 4
9. hurannneru 3
10. haichijin 1
Ввод
11
haiwee 15
haiweebasu 4
haichijin 1
hautsuu 15
hurannneru 3
huruni 8
hotto 125
horumon 15
howaito 23
hurasuko 34
hukku 1
2
h
k
Сегодня в завтрашний день могут
смотреть не только лишь все,
а мы в будущее – можем

50. третья мысль

Дерево
корень
k
h
предсказания
1. hotto 125
2. hurasuko 34
3. howaito 23
4. haiwee 15
5. hautsuu 15
6. horumon 15
7. huruni 8
8. haiweebasu 4
9. hurannneru 3
10. haichijin 1
hukku 1
Ввод
11
haiwee 15
haiweebasu 4
haichijin 1
hautsuu 15
hurannneru 3
huruni 8
hotto 125
horumon 15
howaito 23
hurasuko 34
hukku 1
2
h
k
Сегодня в завтрашний день могут
смотреть не только лишь все,
а мы в будущее – можем

51. третья мысль

Дерево
корень
k
h
предсказания
1. hotto 125
2. hurasuko 34
3. howaito 23
4. haiwee 15
5. hautsuu 15
6. horumon 15
7. huruni 8
8. haiweebasu 4
9. hurannneru 3
10. haichijin 1
Вывод
фраза
результат
k
h
Сегодня в завтрашний день могут
смотреть не только лишь все,
а мы в будущее – можем

52. третья мысль

Дерево
корень
k
h
предсказания
1. hotto 125
2. hurasuko 34
3. howaito 23
4. haiwee 15
5. hautsuu 15
6. horumon 15
7. huruni 8
8. haiweebasu 4
9. hurannneru 3
10. haichijin 1
Вывод
фраза
результат
k
h
Сегодня в завтрашний день могут
смотреть не только лишь все,
а мы в будущее – можем

53. третья мысль

Дерево
корень
k
h
предсказания
1. hotto 125
2. hurasuko 34
3. howaito 23
4. haiwee 15
5. hautsuu 15
6. horumon 15
7. huruni 8
8. haiweebasu 4
9. hurannneru 3
10. haichijin 1
Вывод
фраза
результат
k
h
Сегодня в завтрашний день могут
смотреть не только лишь все,
а мы в будущее – можем

54. третья мысль

Дерево
корень
k
h
предсказания
1. hotto 125
2. hurasuko 34
3. howaito 23
4. haiwee 15
5. hautsuu 15
6. horumon 15
7. huruni 8
8. haiweebasu 4
9. hurannneru 3
10. haichijin 1
Вывод
фраза
результат
k
h
hotto
hurasuko
howaito
haiwee
hautsuu
horumon
huruni
haiweebasu
hurannneru
haichijin
Сегодня в завтрашний день могут
смотреть не только лишь все,
а мы в будущее – можем

55. Проблема?

А нет её, всё прошло

56. ВСЕМ СПАСИБО