Динамический поиск и отображение

Question

У меня большая загрузка документов, текстовых файлов, по которым я хочу найти релевантный контент. Я видел инструмент поиска, не могу вспомнить, где реализован хороший метод, как я описал в моем требовании ниже.

Мое требование следующее:

• Мне нужна оптимизированная функция поиска: я снабжаю эту функцию поиска списком (одним или несколькими) частично-полными (или полными) словами, разделенными пробелами.
• Затем функция находит все документы, содержащие слова, начинающиеся или равные первому слову, затем выполняет поиск этих найденных документов таким же образом, используя второе слово, и так далее, в конце которого она возвращает список, содержащий фактические найденные слова связаны с документами (название и местонахождение), содержащими их, для полного списка слов.
• Документы должны содержать все слова в списке.
• Я хочу использовать эту функцию для поиска по типу, чтобы я мог отображать и обновлять результаты в виде древовидной структуры в режиме реального времени.

Возможный подход к решению, которое я нашел, заключается в следующем: Я создаю базу данных (скорее всего, используя mysql) с тремя таблицами: «Документы», «Слова» и «Word_Docs». ​​

• «Документы» будут иметь (idDoc, Name, Location) всех документов.
• «Слова» будут иметь (idWord, Word) и будут списком уникальных слов из всех документов (конкретное слово появляется только один раз).
• «Word_Docs» будет иметь (idWord, idDoc) и будет списком уникальных комбинаций идентификаторов для каждого слова и документа, в котором оно появляется.

Затем вызывается функция с содержимым поля редактирования при каждом нажатии клавиши (кроме пробела):

• строка токенизирована
• (здесь мои колеса немного крутятся): я уверен, что можно создать один оператор SQL для возврата требуемого набора данных: (actual_words, doc_name, doc_location); (Я не горячий номер с SQL), альтернативно последовательность вызовов для каждого токена и разбора неповторяющихся idDocs?
• этот набор данных (/ list / array) затем возвращается

Затем отображается возвращенный список содержимого:

например: вызывается с: "seq sta cod" отображает:

sequence - start - code - Counting Sequences [file://docs/sample/con_seq.txt]
         - stop - code - Counting Sequences [file://docs/sample/con_seq.txt]
sequential - statement - code - SQL intro [file://somewhere/sql_intro.doc]

(и-так далее)

Это оптимальный способ сделать это? Функция должна быть быстрой, или она должна вызываться только при пробеле? Должен ли он предложить завершение слова? (Получил слова в базе данных) По крайней мере это предотвратит бесполезные вызовы функции для слов, которые не существуют. Если завершение слова: как это будет реализовано?

(Может быть, SO также может использовать этот тип поискового решения для просмотра тегов? (В правом верхнем углу главной страницы))

Answer 1

То, о чем вы говорите, называется инвертированным индексом или списком рассылки и действует аналогично тому, что вы предлагаете и что предлагает Меки. Там много литературы об инвертированных индексах; статья в Википедии - хорошее место для начала.

Лучше, чем пытаться создать его самостоятельно, использовать существующую реализацию инвертированного индекса. И MySQL, и последние версии PostgreSQL по умолчанию имеют полнотекстовую индексацию. Вы также можете проверить Lucene для независимого решения. При написании инвертированного хорошего индекса нужно учесть много вещей, включая токенизацию, основание, многословные запросы и т. Д., И т. Д., И готовое решение сделает все за вас.

Answer 2

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

1. Найти все уникальные слова в текстовом файле. Это разбивает текстовый файл по пробелам на слова и добавляет каждое слово в список, если он еще не найден в этом списке.

2. Возьмите все слова, которые вы нашли, и отсортируйте их по алфавиту; самый быстрый способ сделать это - использовать Three Way Radix QuickSort . Этот алгоритм сложно превзойти по производительности при сортировке строк.

3. Записать отсортированный список на диск, одним словом в строке.

4. Когда вы теперь хотите найти файл документа, полностью его проигнорируйте, вместо этого загрузите индексный файл в память и используйте двоичный поиск, чтобы выяснить, есть ли слово в индексном файле или нет. Бинарный поиск трудно превзойти при поиске больших отсортированных списков.

В качестве альтернативы вы можете объединить шаг (1) и шаг (2) в один шаг. Если вы используете InsertionSort (который использует бинарный поиск, чтобы найти правильную позицию вставки для вставки нового элемента в уже отсортированный список), у вас не только есть быстрый алгоритм, чтобы узнать, есть ли слово в списке или нет, в случае, если это не так, вы сразу получаете правильную позицию для вставки, и если вы всегда вставляете новые, подобные этим, у вас автоматически будет отсортированный список, когда вы перейдете к шагу (3).

Проблема в том, что вам нужно обновлять индекс при каждом изменении документа ... однако, разве это не будет верно и для решения для базы данных? С другой стороны, решение для базы данных дает вам некоторые преимущества: вы можете использовать его, даже если документы содержат так много слов, что индексные файлы больше не помещаются в память (маловероятно, поскольку даже список всех английских слов будет вписывается в память любого обычного пользователя ПК); однако, если вам нужно загрузить индексные файлы огромного количества документов, проблема с памятью может стать. Хорошо, вы можете обойти это, используя хитрые уловки (например, поиск непосредственно в файлах, которые вы отображали в память, используя mmap и т. Д.), Но это те же самые уловки, которые базы данных уже используют для быстрого поиска, поэтому зачем изобретать заново колесо? Кроме того, вы также можете предотвратить проблемы блокировки между поиском слов и обновлением индексов при изменении документа (то есть, если база данных может выполнить блокировку для вас или может выполнить обновление или обновления как элементарную операцию). Для веб-решения с AJAX-вызовами для обновления списка, вероятно, лучше использовать базу данных (мое первое решение вполне подходит, если это локально запущенное приложение, написанное на языке низкого уровня, таком как C).

Если вы чувствуете, что делаете все за один вызов select (что может быть неоптимально, но когда вы динамически обновляете веб-контент с помощью AJAX, это обычно оказывается решением, вызывающим наименьшую головную боль), вам нужно присоединиться ко всем трем таблицам все вместе. Пусть SQL немного ржавый, но я попробую:

SELECT COUNT(Document.idDoc) AS NumOfHits, Documents.Name AS Name, Documents.Location AS Location 
FROM Documents INNER JOIN Word_Docs ON Word_Docs.idDoc=Documents.idDoc 
INNER JOIN Words ON Words.idWord=Words_Docs.idWord
WHERE Words.Word IN ('Word1', 'Word2', 'Word3', ..., 'WordX')
GROUP BY Document.idDoc HAVING NumOfHits=X

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

Answer 3

Google Desktop Search или аналогичный инструмент может удовлетворить ваши требования.

Answer 4

Не уверен насчет синтаксиса (это синтаксис сервера sql), но:

-- N is the number of elements in the list

SELECT idDoc, COUNT(1)
FROM Word_Docs wd INNER JOIN Words w on w.idWord = wd.idWord
WHERE w.Word IN ('word1', ..., 'wordN')
GROUP BY wd.idDoc
HAVING COUNT(1) = N

То есть без использования лайков. С такими вещами НАМНОГО сложнее.