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

Question

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

Мое требование заключается в следующем:

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

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

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

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

• строка токенизирована
• (здесь у меня колеса немного крутятся):Я уверен, что можно создать один оператор SQL для возврата требуемого набора данных:(фактические_слова, имя_документа, местоположение_документа);(Я не очень разбираюсь в 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

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

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

Answer 2

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

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

2. Возьмите все найденные слова и отсортируйте их по алфавиту;самый быстрый способ сделать это — использовать Быстрая сортировка по трехсторонней системе счисления.Этот алгоритм трудно превзойти по производительности при сортировке строк.

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

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

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

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

Если вам хочется сделать все это за один вызов выбора (что может быть неоптимально, но когда вы динамически обновляете веб-контент с помощью 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

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

Answer 3

Не уверен насчет синтаксиса (это синтаксис сервера 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

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

Answer 4

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