Искать много строк по очень большому тексту
У меня около 2 миллионов строк, и мне нужно искать каждую из них по текстовым данным объемом 1 ТБ. Поиск по всем из них — не лучшее решение, поэтому я думал о лучшем способе создания структуры данных, такой как trie для всех строк. Другими словами, три, в котором каждый узел в этом слове. Я хотел спросить, есть ли хороший алгоритм, структура данных или библиотека (на C ++) для этой цели?
Позвольте мне быть более информативным в этом вопросе, ребята,
Например, у меня есть эти строки:
s1- «Я люблю тебя» s2- «Как дела» s3- «Как дела, чувак»
И у меня есть много текстовых данных, таких как:
t1- «Привет, меня зовут Омид, и я люблю компьютеры. Как вы, ребята?» t2- «Каждое ваше желание будет исполнено, они говорят мне …» t3
t4
,
,
,
T10000
Затем я хочу рассмотреть каждый из текстов и найти для них каждую из строк. Наконец, для этого примера я бы просто сказал: t1 содержит s1 и ничего больше.
Я ищу эффективный способ поиска строк, но не глупо для каждого из них каждый раз.
Решение
Прошу прощения за публикацию ответа только по ссылке, но если вы не возражаете против прочтения исследовательской работы, мне кажется, что окончательная ссылка на алгоритмы сопоставления строк http://www-igm.univ-mlv.fr/~lecroq/string/ и следующее Научно-исследовательская работа Simone Faro и Thierry Lecroq, где они сравнили относительную производительность не менее чем 85 различных алгоритмов сопоставления строк. Я уверен, что среди них есть один, соответствующий вашим потребностям.
Другие решения
Я настоятельно рекомендую вам использовать CLucene (http://clucene.sourceforge.net/), который является портом из проекта Apache Lucene. Это создаст вам перевернутый индекс и сделает поиск текста очень быстрым. Если изменение языка является вариантом, рассмотрите возможность сделать это в Java, поскольку версия CLucene немного устарела. Это будет медленнее, но имеет больше возможностей.