Префикс поиска с полмиллиарда строк

У меня есть список из 500 мил строк. Строки являются буквенно-цифровыми символами ASCII различного размера (обычно от 2 до 30 символов). Кроме того, они представляют собой отдельные слова (или комбинацию слов без пробелов типа «helloiamastring»).

Мне нужен быстрый способ проверить цель, скажем «привет». Результатом должны быть все строки из списка 500mil, которые начинаются с «привет» (например, «hithere», «hihowareyou» и т. Д.). Это должно быть быстрым, потому что каждый раз, когда пользователь набирает что-либо, будет появляться новый запрос, поэтому, если он напечатает «привет», будут показаны все строки, начинающиеся с «привет» из списка 500 млн, если он наберет «эй», все строки, начинающиеся с «эй», будут показаны и т. д.

Я пробовал с Tries algo, но объем памяти для хранения 300-мильных строк просто огромен. Для этого мне потребуется 100 ГБ + барабан. И я уверен, что этот список вырастет до миллиарда.

Что такое быстрый алгоритм для этого варианта использования?

PS В случае, если нет быстрого варианта, лучшей альтернативой было бы ограничить людей, чтобы ввести, по крайней мере, 4 символа, прежде чем появятся результаты. Есть ли быстрый способ получить результаты?

6 Solutions collect form web for “Префикс поиска с полмиллиарда строк”

Вам нужен Direct Acilic Word Graph или DAWG. Это обобщает предложение @ greybeard использовать стебли.

См., Например, обсуждение в разделе 3.2 этого .

Если строки отсортированы, то двоичный поиск является разумным. В качестве ускорения вы могли бы поддерживать словарь всех возможных биграмм («aa», «ab» и т. Д.), Где соответствующие значения являются первым и последним индексом, начинающимся с этого bigram (если они есть), и поэтому в O(1) time zero in на гораздо меньшем подсписке, который содержит строки, которые вы ищете. Как только вы найдете совпадение, выполните линейный поиск вправо и влево, чтобы получить все остальные совпадения.

Если вы хотите заставить пользователя набрать не менее четырех букв, например, вы можете сохранить карту памяти, память или диск, где ключи – все комбинации из 4 букв (их не слишком много, если они нечувствительны к регистру , в противном случае вы можете ограничить до трех), а значения – это список позиций всех строк, начинающихся с комбинации.

После того, как пользователь набрал три (или четыре) буквы, у вас есть сразу все возможные строки. С этого момента вы просто зацикливаете на этом подмножестве.

В среднем это подмножество достаточно мало, т. Е. 500 М делится на 26 ^ 4 … как пример. На самом деле больше, потому что, вероятно, не все наборы из 4 букв могут быть префиксом для ваших строк.

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

Если вы не хотите использовать какую-либо базу данных, вы должны создать некоторые связанные с данными процедуры, ранее существовавшие во всех механизмах баз данных:

  1. Не пытается загрузить все данные в память.
  2. Используйте фиксированную длину для всей строки. Это увеличивает потребление памяти памяти, но значительно уменьшает время поиска (i-я строка может быть найдена в позиции L * i байтов в файле, где L – фиксированная длина). Создайте дополнительный механизм для работы с чрезвычайно длинными строками: сохраните его в другом месте и используйте специальные указатели.
  3. Сортировка всех строк. Вы можете использовать сортировку слияния, чтобы сделать это без загрузки всех строк в памяти за один раз.
  4. Создание индексов (адрес первой строки начинается с «a», «b», …) также могут быть созданы индексы для 2 грамм, 3 грамма и т. Д. Индексы могут быть помещены в память для увеличения скорости поиска.
  5. Используйте расширенные стратегии, чтобы избежать полной регенерации индексов при обновлении данных: разбивайте данные на несколько файлов по первым буквам и обновляйте только затронутые индексы, создавайте пустые пробелы в данных, чтобы уменьшить влияние процедур чтения-изменения-записи, создать кэш для новые строки, прежде чем они будут добавлены в основное хранилище и поиск в этом кеше.
  6. Используйте кеш запросов для быстрой обработки популярных запросов.

В этой гипотезе, где индексируемые строки не связаны ни с какой другой информацией (например, с другими столбцами в одной строке), существует относительно небольшая разница между полным индексом и сохранением строк, отсортированных в первую очередь (как, например, в некоторой разнице , но не так сильно, как вы надеетесь). В свете растущего характера списка и стоимости его обновления, возможно, противоположный подход позволит лучше выполнить компромисс производительности, который вы ищете.

Для любого заданного символа в любом заданном месте в строке ваш базовый случай состоит в том, что ни одна строка не существует, содержащая эту букву. Например, после того, как «hello» было введено, если следующая буква набрана «t», тогда ваш базовый пример состоит в том, что строка «hellot» не начинается. Существует конечное число символов, которые могли бы следовать «привет» в местоположении 5 (скажем, 26). Вам нужно 26 пространств фиксированной длины, в которых будет храниться информация о символах, которые следуют «привет» в местоположении 5. Каждое пространство либо говорит «ноль», если нет строки, в которой, например, «t» следует «привет» или содержит число адресов для хранения данных, с помощью которых можно перейти к поиску списка символов, для которых одна или несколько строк включают этот символ, следующий за «hellot» в местоположении 6 (или использовать абсолютные адреса хранилища данных, хотя только относительная адресация позволяет алгоритм, который я предлагаю поддерживать бесконечное количество строк бесконечной длины без каких-либо изменений, чтобы увеличить указатели при увеличении списка).

Затем алгоритм может перемещаться вперед по этим данным, хранящимся на диске, создавая дерево начальных строк в памяти по мере его использования и избегая задержек, вызванных чтениями с произвольным доступом. Для индекса in-memory просто сохраните часть дерева, ближайшего к корню в памяти. После того, как пользователь набрал «привет», и алгоритм отслеживал, что информация об одной или нескольких строках, начинающихся с «hellot», существует на адресе X хранения данных, алгоритм находит один из двух типов списков в местоположении X. Либо это другая последовательность например, 26 фиксированных пространств с информацией о персонажах, следующих за «hellot» в местоположении 6, или это заранее выделенный блок пространства, содержащий все пост-исправления, которые следуют за «hellot», в зависимости от того, сколько таких пост-исправлений существовать. Как только достаточно исправлений, которые используют традиционный алгоритм поиска и / или сортировки для обновления и поиска, список пост-исправлений не позволяет обеспечить преимущества производительности, которые вы желаете, он делится и заменяется последовательностью, например, 26 фиксированных пространств.

Это связано с предварительным распределением относительно значительного объема дискового хранилища, с компромиссом, что ваше дерево может поддерживаться в отсортированной форме без необходимости перемещать что-либо вокруг для большинства обновлений, и ваши поисковые запросы могут быть сформированы в полном объеме за одно последовательное чтение , Он также обеспечивает большую гибкость и, вероятно, требует меньше места для хранения данных, чем решение, основанное на сохранении самих строк в виде строк фиксированной длины.

Прежде всего, я должен сказать, что тег, который вы должны добавить для своего вопроса, это «Информационный поиск».

Я думаю, что использование Apache Lucene PrefixQuery – лучший способ справиться с подстановочными запросами. У Apache есть версия Python, если вам удобно работать с python. Но чтобы использовать Apache lucent для решения вашей проблемы, вы должны сначала знать об индексировании ваших данных (что является тем, что ваши данные будут сжаты и сохранены более эффективным образом).

Также поиск индексации и подстановки шаблона в ИК-книге даст вам лучшее видение.

  • Строковое манипулирование с помощью обычного выражения или выражений
  • Как я могу преобразовать строки типа «\ u5c0f \ u738b \ u5b50 \ u003a \ u6c49 \ u6cd5 \ u82f1 \ u5bf9 \ u7167" на иероглифы
  • Декодирование с двойной кодировкой utf8 в Python
  • Как получить полезный результат из подпроцесса?
  • Предупреждение pep8 для строки регулярного выражения в Python, Eclipse
  • Типы Python str и Unicode
  • Что такое чистый способ преобразования процентной ставки строки в float?
  • pandas заменяет (стирает) разные символы из строк
  • Лучший способ преобразовать строку в байты в Python 3?
  • Почему некоторый код детерминирован в Python2 и не является детерминированным в Python 3?
  • Как эффективно фильтровать строку в длинном списке слов в Python / Django?
  • Python - лучший язык программирования в мире.