Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 12.06.2011, 09:42
Новичок

Отправить личное сообщение для zhazhah Посмотреть профиль Найти все сообщения от zhazhah
 
Регистрация: 28.01.2011
Сообщений: 7

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

Кусок текста с документации Яндекс.Сервера
Код:
Для каждого слова в документе запоминается его позиция в виде идентификатора документа, 
номера предложения и номера слова в предложении. Список таких троек (словопозиций) хранится в 
файлах indexinv и indexkey. В этих же файлах хранятся зоны и атрибуты документов, используемые 
при поиске по зонам и атрибутам (например, html-заголовок или подпись к картинке), а также некоторая 
служебная информация. Кроме того, в файлах indexarc и indexdir по умолчанию сохраняется текст 
документов без элементов форматирования. Эта информация используется при поиске, если требуется 
получать отрывки текста документа, содержащие найденные слова.
Прочитав несколько глав из книги "Введение в информационный поиск" я понял что простейший индекс строится таким образом.

фраза->документ

Код:
книга 1 3 6...n  //т.е 1 3 6 это ID документа в котором встречается фраза.
поиск 3 5 9...n // и документов в которых встречается данное слово может быть очень много
вот и проблема как искать по этому файлу(индексу). Допустим что мы проиндексировали какой то сайт и получили около 600 тысяч фраз и каждая фраза встречается в документах от 1 до 90 тыс.
как искать по такому индексу?
правильно ли я всё расписал?
у меня одна мысль тупо читать файл и сравнивать((
  #2  
Старый 12.06.2011, 10:02
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Простой случай поисковой (инверсной) индексации - словарь, состоящий из пар слово-список индексов. Индекс - некая структура, например, для одного документа она может быть такой - (номер страницы, номер слова на странице).
Вася - [(1,5), (10, 30)]
Петя - [(2,10),(3,15),(10,31)]
В таком случае, если нужен Вася, то в результатах поиска выдаются 1 и 10-я страницы, на которых при надобности выделяются соответствующие по номеру слова.
  #3  
Старый 12.06.2011, 10:19
Новичок

Отправить личное сообщение для zhazhah Посмотреть профиль Найти все сообщения от zhazhah
 
Регистрация: 28.01.2011
Сообщений: 7

Спасибо, а как быстро найти Васю без cравнивания всех записей?
  #4  
Старый 12.06.2011, 10:25
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Любая словарная структура - Dictionary, Map
Они строятся на основе хэш-таблиц или сбалансированных деревьев.
  #5  
Старый 12.06.2011, 10:45
Новичок

Отправить личное сообщение для zhazhah Посмотреть профиль Найти все сообщения от zhazhah
 
Регистрация: 28.01.2011
Сообщений: 7

Цитата:
Любая словарная структура - Dictionary, Map
Они строятся на основе хэш-таблиц или сбалансированных деревьев.
Спасибо, знаю про Map коллекции только благодаря Java но как это работает, как удается найти нужный ключ не перебирая всего списка не понимаю, а найти необходимую информацию не получаеца...
  #6  
Старый 12.06.2011, 11:05
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

вкратце есть тут
http://algolist.ru/ds/index.php
А вообще - книжки по алгоритмам и структурам данных.
Да и в инете информации полно.
  #7  
Старый 12.06.2011, 11:57
Новичок

Отправить личное сообщение для zhazhah Посмотреть профиль Найти все сообщения от zhazhah
 
Регистрация: 28.01.2011
Сообщений: 7

Спасибо буду читать)
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Реализация алгоритма Ху (Hu) RARIA Графы 2 25.12.2009 00:47
реализация графа на с++ гость Графы 6 24.12.2009 20:24
реализация ГОСТ 34.11 на С++ Сашка Реализация, исходники, языки 1 21.02.2009 20:35
Реализация ввода Олег Павлыш Реализация, исходники, языки 13 17.03.2008 23:16
реализация B++ на сайте Dok Реализация, исходники, языки 0 30.11.2006 14:36