Соответствие строки

Question

Позвольте мне объяснить проблему:

1. Допустим, у меня есть библиотека, библиотека содержит много книг, каждая книга содержит главы, каждая глава содержит строку (и строка начинается и заканчивается точкой ".").
2. Последовательность снова, библиотека -> книга -> глава -> строка.
3. Я извлек строки из книг, назовем их «строки книг».
4. У меня есть система, в которой пользователь может ввести строку в форму поиска, и система должна вернуть точное совпадение введенной строки из "строк книги". Если введенная строка не совпадает ни с одной строкой из строк книги, ничего не будет возвращено.

Я думаю об этом и нашел решение, я буду MD5 всех строк книг и сохраню строки хешированных книг. Когда пользователь вводит строку для поиска, я тоже хеширую ее и ищу совпадения в строках хешированных книг. Он дешевле (32 или 64 символа для каждой строки), быстрее простого поиска и возвращает только точное совпадение (я).

Есть ли у вас какие-либо комментарии, идеи, лучшие решения?

P.S. Как называется такой алгоритм? поиск или совпадение?

Answer 1

Существует множество алгоритмов поиска в строках, начиная от простых методов, таких как алгоритм Бойера-Мура , и заканчивая сложными структурами данных, такими как деревья суффиксов . Их полное представление можно найти в:

• Gusfield, Dan (1999), Алгоритмы на строках, последовательностях и деревьях. Кембридж: Университетская пресса.

Однако для вашего случая, вероятно, имеет смысл разделить текст книги на отдельные токены (слова) и сохранить их в индексе (например, просто на карте, или использовать полную структуру для индексации и поиска, например: Lucene ).

Answer 2

Это не плохо, но вы должны исследовать Lucene. это общедоступный инструмент для индексирования текста и поиска, реализованный на многих языках, одним из которых является .Net. (на каком языке вы работаете?) Основная модель заключалась в предоставлении контента в сегменте рынка paritcula (многочисленные статьи в журналах, отрывки из книг и т. д.). Lucene работал очень хорошо для нас.

Lucene

Answer 3

Он называется хэшированием и может рассматриваться как поиск или сопоставление.

Вы должны убедиться, что ваш MD5-хэш правильный, также сравнив строку, которая использовалась для генерации хеша, чтобы у вас не было ложных срабатываний .

Еще одна вещь, которую стоит учесть, это то, что может быть полезно сделать поддержку какого-то типа , начинающегося с поиска. Рассмотрим

Mary Queen of Scots
Mary Livingston
Mary Had a Little Lamb, and other silly stories

A начинается с поиска Мэри, должен вернуть эти три записи и, возможно, больше. Несмотря на то, что хеш-код MD5 является быстрым, методы, представленные в других ответах, также должны быть рассмотрены, чтобы найти наилучшее соотношение выгод и затрат для ваших обстоятельств.

Answer 4

Вместо этого вы должны конвертировать каждую главу книги в дерево суффиксов . Дерево суффиксов - это тип Trie (упоминается как divo).

Суффикс-дерево специально предназначено для использования в быстром текстовом поиске. Одно из преимуществ суффикс-дерева состоит в том, что поиск строки длиной n - это O (n) времени. Это так же хорошо (асимптотически), как и идея вашего алгоритма (поскольку хеширование строки занимает O (n) времени), но гораздо более гибко, поскольку будет работать даже для частичных предложений. Поиск сводится к поиску предложений, если вы начинаете / заканчиваете поиск точкой.

Уточнение. Точнее, у вас будет одно суффиксное дерево для всего.

Answer 5

Возможно, вы захотите использовать Trie или другую древовидную структуру данных для хранения ваших строковых данных.

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

• Поиск данных в дереве выполняется в наихудшем случае быстрее (O), по сравнению с несовершенной хеш-таблицей. Несовершенная хеш-таблица может иметь ключ столкновения. Ключевое столкновение является отображение хеш-функции разных ключи к той же позиции в хэше Таблица. Скорость поиска в худшем случае в несовершенная хеш-таблица - это время O (N), но гораздо более типичным является O (1), с O (м) время, потраченное на оценку хеша.

• В дереве три столкновения разных ключей отсутствуют.

• Ведра в дереве, которые аналогичны корзинам хеш-таблиц, которые ключи магазина хранятся только необходимо, если один ключ связан с более чем одним значением.
• Нет необходимости предоставлять хеш-функцию или изменять хеш функции как дополнительные ключи добавляются к Trie.
• Три могут обеспечить алфавитный порядок записей по ключу.

У попыток также есть некоторые недостатки:

• В некоторых случаях попытки поиска могут выполняться медленнее, чем в хеш-таблицах данные, особенно если данные прямой доступ к жесткому диску или какое-то другое вторичное запоминающее устройство где время произвольного доступа велико по сравнению с основной памятью.
• Нелегко представить все ключи в виде строк, таких как плавающие номера точек, которые могут иметь несколько строковые представления для того же число с плавающей запятой, например 1, 1,0, 1,00, +1,0 и т. Д.
• Попытки часто менее экономичны, чем хеш-таблицы.

(см. http://en.wikipedia.org/wiki/Trie)

Answer 6

Я согласен с Trie - с одним дополнением, использую алгоритм soundx для преобразования строки для идентификатора / узла Trie - так что неправильные написания учитываются

Answer 7

A Trie - лучший подход. Это то, что также называется суффиксной картой. Преимущество использования Trie по сравнению с вашей идеей хеширования состоит в том, что с помощью Trie вы можете очень легко отображать синтаксис автозаполненного типа. Время нахождения слова - O (n), где n - длина слова. В каждом узле вашего Trie вам нужно будет хранить список книг, содержащих определенное слово.

Answer 8

Во-первых, это действительно звучит так, как будто вы должны использовать базу данных - это в значительной степени именно то, для чего нужны базы данных. (Если вы хотите, чтобы это было встроено в ваше собственное приложение, посмотрите SQLite , облегченную СУБД, предназначенную для использования в качестве встроенной библиотеки.)

Во-вторых, не совсем верно, что ваше хеш-решение будет возвращать только точные совпадения ... Поскольку дайджест MD5 составляет 128 битов, это означает, что любая данная пара строк имеет шанс 1-в-2 ^ 128 с получением то же хеш-значение. Да, это небольшое число, но если у вас много книг, у вас будет много пар строк. Итак, после сравнения значений хеш-функции вам потребуется выполнить полнотекстовое сравнение, чтобы исключить ложные срабатывания.

Answer 9

Это называется хешированием. Ваш метод может работать, но он не очень гибкий. Опять же, вы будете получать только точные совпадения. Также возможно, что два прообраза совместно используют одно и то же изображение (хэш двух разных строк с одинаковым значением), но это крайне маловероятно, так что это не является реальной проблемой. Я бы рекомендовал против этого из-за нехватки гибкости, но если это не беспокоит вас, то я думаю, это будет работать для вас. По сути, это тот же метод, который люди используют для хранения и проверки паролей (за исключением того, что вы, очевидно, не используете никаких «соленых» значений).