Список `k` слов, начинающихся с фиксированного префикса, в порядке убывания их частоты

У меня есть список примерно из 10^5 английских слов и их начальная частота. Я хочу написать программу предложения завершения слов, которая будет возвращать список максимальных k слов, начиная с заданного префикса, отсортированных в порядке убывания их частоты. Структура данных также должна иметь возможность обновлять счетчик частоты слова на 1 (всякий раз, когда слово используется).

Например, учитывая префикс «engin» и k = 3, он должен возвращать следующий список: {{17, «engine»}, {10, «engineer»}, {4, «engineering»}}

Значение k должно быть в пределах [1, 15].

Trie структуры данных должно было быть достаточно, если сортировка по частоте не была проблемой, но это так. Может ли кто-нибудь подсказать мне какую-либо структуру данных или какой-либо подход к решению этой проблемы?

Примечание. Структура данных Trie занимает слишком много места. Похоже, я не могу позволить себе более 10MB для этой структуры данных. Кроме того, если я использую максимальные кучи, связанные с узлами trie (по крайней мере, до 3/4 глубины), потребление памяти становится ОГРОМНЫМ.

На данный момент я пробовал это: поддерживать 4 отсортированных набора (указателей, указывающих на строки). Набор i представляет собой список указателей на строки из string length >= i отсортированных

  • Лексикографический порядок первых i букв строки
  • Если конфликтуют, в порядке убывания частоты
  • При повторном столкновении в любом порядке (незначительно)

Это хорошо работает, учитывая, что для инициализации мне требуется O(4nlog2(n)) времени и O(nlog2(n)) пространства. Для каждого запроса у меня сложность времени поиска O (log2 (n)), плюс обход не более примерно 100 слов в худшем случае. Для обновления частоты слова требуется время O(8*log2(n)).


sorting algorithm data-structures n-gram trie
person crysoberil    schedule 29.09.2014    source источник
comment
Простой запрос к БД недостаточно быстр? Кроме того, вместо немедленного обновления частот вы можете сделать это, например. раз в день для реорганизации структуры поиска.   -  person Henry    schedule 29.09.2014
comment
@ Генри Нет, мне нужно гораздо более быстрое решение, желательно с использованием структуры данных в памяти.   -  person crysoberil    schedule 29.09.2014
comment
Думали ли вы о том, что вам нужна максимальная куча?   -  person Squidly    schedule 29.09.2014

Ответы (2)


arrow_upward
1
arrow_downward

Это можно сделать с помощью комбинации двух структур данных: trie и дерева сегментов. (Если словарь статичен и k не очень большой).

После построения trie для вашего словаря дополните каждый узел trie индексами первого/последнего слова, принадлежащего этому узлу. Например, узел «engin» может хранить индекс 1001 для «engine» и индекс 1003 для «engineering».

При поиске списка из k слов начните с поиска заданного префикса в дереве. Затем используйте индексы первого/последнего слова для выполнения запросов с максимальным диапазоном k. После каждого запроса временно установите подсчет частоты найденного слова на -1.

Используйте структуру данных дерева сегментов для запросов максимального диапазона. (Подробности см. в руководстве на TopCoder).

Такой подход позволяет обрабатывать каждый запрос за время O(prefix_size + k * log(dict_size)). Для обновления счетчика требуется время O(log(dict_size)) . Начальные частоты загружаются за время O(dict_size).

Другой альтернативой является хранение отсортированного массива пар k_max {счетчик, индекс} в каждом узле дерева.

Начальные частоты должны быть обновлены слиянием на каждом узле в восходящем порядке (с DFS) за время O(k_max * dict_size). Для каждого обновления счетчика требуется время O(k_max * word_length). Запросы Top-k обслуживаются за время O(prefix_size). Недостатком являются гораздо более высокие требования к памяти.

person Evgeny Kluev    schedule 29.09.2014

arrow_upward
0
arrow_downward

Почему бы не попробовать? Вы можете использовать дополнительное поле данных для счетчика и добавить алгоритм сортировки в алгоритм поиска. Обновление счетчика и попытки также происходит быстро. Если вам нужны только k максимальных/верхних ребер, тогда это быстрее, потому что вам не нужно сортировать все.

person Gigamegs    schedule 29.09.2014
comment
Случай, когда это не очень эффективно: например, я хочу предложить префикс 'a' и k = 10. Хотя мне нужно всего 10 предложений, в этом случае trie должен пройти все слова, начинающиеся с a, чтобы построить список, который составляет огромную часть дерева. - person crysoberil; 29.09.2014
comment
Если вам нужны только k верхних ребер из a, это быстрее, чем сортировать все egdes!! - person Gigamegs; 29.09.2014
comment
@ user1362452: В вашем случае с 10 ^ 5 словами ваш результирующий набор слов, начинающихся с «а», будет меньше 10 ^ 4. И хотя вам нужно обходить их, вам не нужно их сохранять. Вы можете построить максимальную кучу из 10 и оставить только 10 слов с наибольшей частотой. Ваш алгоритм выбора становится O(n log k), где n — это количество слов, начинающихся с префикса, а k — это количество слов, которые вы хотите выбрать. Предполагая, что обновления происходят редко по сравнению с запросами, это очень эффективный способ. И это легко реализовать. - person Jim Mischel; 30.09.2014
comment
@JimMischel Я обновил свой вопрос. Сложность пространства вызывает беспокойство. Не могли бы вы взглянуть на мое текущее решение и предложить какие-либо улучшения? - person crysoberil; 05.10.2014