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

Question

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

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

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

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

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

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

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

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

например: вызывается: "сл STA треска" дисплеях:

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] 

(and-so-on)

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

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

Answer 1

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

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

Answer 2

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

-- 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 3

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

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

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

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 4

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