В самом ли деле нет альтернативы "инвертированным файлам" как способу организации индекса для SE?
Нет, широко используются и сигнатурные файлы, в которых применяются так называемые n-граммы, которые затем каким-то образом хешируются и формируют сигнатуру слов.
И - все ли SE используют "инвертированные файлы" в качестве индексов?
Вот и спросите у разработчиков. ;) Насколько я знаю, большинство поисковиков используют.
Вообще говоря, имея в своем распоряжении инвертированный файл, - можно ВОССТАНОВИТЬ исходный файл ... (правда, наверное, в нем будут потеряны мелкие детали, - типа заглавных букв!)
По инвертированному файлу можно получить только некие координаты каждого слова в текста, сам по себе восстанавливать он ничего не позволяет.
но - хранят "у себя" наряду с инвертированными файлами также весь проиндексированный контент в виде "обычных" (не-инвертированных) файлов?
Контент, из которого получаются сниппеты с подсвеченными ключевыми словами, обычно хранится в специальном хранилище, которое и адресуется координатами из инвертированных файлов.
Значит, вы однозначно не советуете пользоваться никакими СУБД вообще?
С них все, естественно, начинают, но быстро спрыгивают.
Я бы посоветовал почитать классическую теорию по информационно-поисковым системам касательно инвертированных файлов и алгоритмов ранжирования, и попробовать по их мотивам написать что-нибудь свое.
Окей, а разве после добавления не нужна пересортировка (и в список ли)?
Добавлении куда? При индексации формируется специальный словарь - лексикон, содержащий нормальные формы слов.
И потом, чего-то я не поняла - разве по списку быстрей пройдёшься
В лексиконе для каждого слова хранятся координаты в списке, по которым можно быстро получить документы, где слово встречается. Поэтому список служит только для быстрой выборки идентификаторов документов (и сопутствующей информации о координатах слов в тексте). Обычно в него ничего не добавляется и не удаляется, так как он формируется за один раз на этапе индексации.
Да, но разве инвертированные файлы не строятся на тех самых b-деревьях?
Нет, конечно. :) B-деревья - это разновидность деревьев, которые дополнительно в своих узлах содержат какие-то данные, а инвертированные файлы - это списки данных.
Соответственно, отсортированное B-дерево может вырождаться в список. ;)
Тем более, необходимы дополнительно алгоритмы сжатия таких файлов
Необязательно. Чем сильнее сожмете, тем больше можете просадить производительность поиска.
Сама структура БД должна быть оптимизирована под алгоритм. Другое дело - в каком формате саму БД хранить.
В каком бы формате поисковая база не хранилась, производительность все равно будет относительно невысокой из-за ненужных операций вроде лексического разбора запросов и прочих радостей, из-за которых все проседает.
Если я сейчас сяду придумывать свой формат хранения базы, буду ваять его... ну, в общем, долго... и неизвестно, что еще наваяю.
А не надо ничего придумывать - все уже придумано до нас. :) Любая поисковая система обычно строится на инвертированных файлах , теория хорошо изучена и общедоступна.
На этапе хранения данных и организации поисковой системы никаких вопросов не возникает - принцип у всех один и тот же. Вопросы появляются только тогда, когда нужно ранжировать документы и формировать сниппеты с подсвеченными словами.
Не помрет, но будет долго ломаться. Пробовала. Результат неутешителен.
Сейчас буду на эту тему мучать оракл
Вообще-то СУБД никак не предназначены для использования в качестве поисковых систем - ни mysql, ни Oracle, ни другие базы. Кроме того, они имеют ограничения по объему информации.
Дело даже не в структурах данных и B-деревьях, а в самой организации СУБД - она служит для совершенно других целей. Максимум, что может дать база данных - это просто набор документов, где встретился искомый термин, так как никакой сортировки по релевантности или другим параметрам, подсветки в сниппетах найденных ключевых слов, группировки документов там нет. Конечно, есть отдельные пристройки под поиск, но они не слишком эффективны, чтобы использовать их на гигабайтных объемах.
Э... А он там нужен? :)
Справочная
Нет, широко используются и сигнатурные файлы, в которых применяются так называемые n-граммы, которые затем каким-то образом хешируются и формируют сигнатуру слов.
Более подробно можно почитать здесь.
Вот и спросите у разработчиков. ;) Насколько я знаю, большинство поисковиков используют.
По инвертированному файлу можно получить только некие координаты каждого слова в текста, сам по себе восстанавливать он ничего не позволяет.
Контент, из которого получаются сниппеты с подсвеченными ключевыми словами, обычно хранится в специальном хранилище, которое и адресуется координатами из инвертированных файлов.
С них все, естественно, начинают, но быстро спрыгивают.
Я бы посоветовал почитать классическую теорию по информационно-поисковым системам касательно инвертированных файлов и алгоритмов ранжирования, и попробовать по их мотивам написать что-нибудь свое.
P.S. Вижу, Вы тоже из Украины? :)
Обновлять частями, конечно. Распределенный индекс, каждая часть которого собирается на своей машине.
Словарь словоформ - это преимущественно статическая структура. Насколько я знаю, у Яндекса и Рамблера в словаре всего-то 100-150 тысяч слов.
А Вы собираетесь запускать второй Google? :)
Да. Зато максимально быстро.
Добавлении куда? При индексации формируется специальный словарь - лексикон, содержащий нормальные формы слов.
В лексиконе для каждого слова хранятся координаты в списке, по которым можно быстро получить документы, где слово встречается. Поэтому список служит только для быстрой выборки идентификаторов документов (и сопутствующей информации о координатах слов в тексте). Обычно в него ничего не добавляется и не удаляется, так как он формируется за один раз на этапе индексации.
Нет, конечно. :) B-деревья - это разновидность деревьев, которые дополнительно в своих узлах содержат какие-то данные, а инвертированные файлы - это списки данных.
Соответственно, отсортированное B-дерево может вырождаться в список. ;)
Необязательно. Чем сильнее сожмете, тем больше можете просадить производительность поиска.
В каком бы формате поисковая база не хранилась, производительность все равно будет относительно невысокой из-за ненужных операций вроде лексического разбора запросов и прочих радостей, из-за которых все проседает.
А не надо ничего придумывать - все уже придумано до нас. :) Любая поисковая система обычно строится на инвертированных файлах , теория хорошо изучена и общедоступна.
На этапе хранения данных и организации поисковой системы никаких вопросов не возникает - принцип у всех один и тот же. Вопросы появляются только тогда, когда нужно ранжировать документы и формировать сниппеты с подсвеченными словами.
Сейчас буду на эту тему мучать оракл
Вообще-то СУБД никак не предназначены для использования в качестве поисковых систем - ни mysql, ни Oracle, ни другие базы. Кроме того, они имеют ограничения по объему информации.
Дело даже не в структурах данных и B-деревьях, а в самой организации СУБД - она служит для совершенно других целей. Максимум, что может дать база данных - это просто набор документов, где встретился искомый термин, так как никакой сортировки по релевантности или другим параметрам, подсветки в сниппетах найденных ключевых слов, группировки документов там нет. Конечно, есть отдельные пристройки под поиск, но они не слишком эффективны, чтобы использовать их на гигабайтных объемах.