Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
 Полнотекстовое индексирование вручную  [new]
Alan008
Member

Откуда: г. Иваново
Сообщений: 52
В системе реализован аналог полнотекстового поиска следующим образом.
Существует таблица-справочник всех уникальных слов, встречающихся в документах.
WordsDict:
ID int, Word varchar(150)
Существует таблица информации о наличии слов в искомых документах.
DocWords:
DocID int, WordID int, WordInd
WordInd - это порядковый номер слова в документе (просто глобальный номер 0, 1, 2...).
Одно и то же слово может встречаться по несколько раз.

На вход поступает запрос: список ID'ов искомых слов (в запрос будет передаваться в виде "WordID IN (1, 100, 567)").
Нужно построить несколько запросов к таблице DocWords:
1) Отобрать все документы, содержащие все переданные слова в любом порядке.
2) Отобрать все документы, содержащие все переданные строго в таком порядке и идущие подряд.
3) Отобрать все документы, содержащие все переданные слова с заданной cтепенью близости (например, на отдалении не более N слов друг от друга, т.е. N в данном случае - дистанция между наиболее удаленными словами).
Реализуем ли каждый из указанных запросов одним SQL-запросом?
Запрос для 1) не очень сложный, я его уже придумал, вам просто для "въезда в задачу". А вот 2-3 подозреваю потребуют CTE, а я их, к сожалению, еще не освоил (

Просьба отнестись к теме как к интересной и необычной алгоритмической задаче, а не советовать "юзайте Full Text Search" ;)
8 окт 12, 16:19    [13285669]     Ответить | Цитировать Сообщить модератору
 Re: Полнотекстовое индексирование вручную  [new]
trew
Member

Откуда: Москва
Сообщений: 2646
Alan008,

12302285
8 окт 12, 17:00    [13285975]     Ответить | Цитировать Сообщить модератору
 Re: Полнотекстовое индексирование вручную  [new]
Alan008
Member

Откуда: г. Иваново
Сообщений: 52
Про похожесть и дистанцию Левенштейна я знаю. Но в данной теме рассматривается точный поиск (с учетом описанных ограничений). Я таблицу WordsDict привел только для понимания, о чем вообще идет речь. В самом запросе слова в виде строк вообще не участвуют, а используются уже строгие ID'ы слов. Никакого нечеткого поиска.
8 окт 12, 17:04    [13286007]     Ответить | Цитировать Сообщить модератору
 Re: Полнотекстовое индексирование вручную  [new]
Winnipuh
Member [заблокирован]

Откуда: Київ
Сообщений: 10428
Alan008
Про похожесть и дистанцию Левенштейна я знаю. Но в данной теме рассматривается точный поиск (с учетом описанных ограничений). Я таблицу WordsDict привел только для понимания, о чем вообще идет речь. В самом запросе слова в виде строк вообще не участвуют, а используются уже строгие ID'ы слов. Никакого нечеткого поиска.


а при чем тут "полнотекстовое" ?

Это какой-то свой велосипед для поиска.
8 окт 12, 17:09    [13286051]     Ответить | Цитировать Сообщить модератору
 Re: Полнотекстовое индексирование вручную  [new]
Alan008
Member

Откуда: г. Иваново
Сообщений: 52
Ну начинается. Велосипед для поиска. Вы сделайте сначала такой велосипед, потом уж говорите, хорош он или плох. Для нечеткого поиска там используется стемминг в справочнике слов: кроме "исходного" варианта написания слова хранится усеченный вариант (основа) данного слова. К решению описанной выше проблемы это отношения не имеет, поэтому я не стал об этом писать.
8 окт 12, 17:13    [13286089]     Ответить | Цитировать Сообщить модератору
 Re: Полнотекстовое индексирование вручную  [new]
Леша777
Guest
Я решал такую задачу следующим образом :

1) находил все документы с со стартовой позицией, куда входит 1 искомое слово.
2) находил следующие n слов в каждом документе за искомым словом и сравнивал их. Если число соответствий равно числу искомых слов, то фраза совпала.

+

DECLARE @PassedWord TABLE (ind TINYINT PRIMARY KEY, WordID INT NOT NULL) -- таблица для переданных слов 

INSERT INTO @PassedWord(ind, WordID) -- заполняем тестовыми данными (ind тоже начинается с 0)
SELECT 0, 123 
UNION ALL
SELECT 1, 567
UNION ALL
SELECT 2, 345 

DECLARE @WordCount INT ; 

-- находим число переданных (после 1 с индесом 0)
SET @WordCount  = 
                  (
                    SELECT 
                            COUNT(*)
                    FROM @PassedWord AS pw	
                    WHERE pw.ind > 0
                  	
                  );
                  
DECLARE @FirstWordID INT ; 

-- находим 1ое искомое слово 
SET @FirstWordID = 
                   (
                   	 SELECT 
                   	        p.WordID
                   	 FROM @PassedWord AS p 
                   	 WHERE p.ind = 0
                   );	  
 
 
SELECT 
        w.DocID  
FROM dbo.DocWords AS w -- все документы которые содержат 1ое искомое слово 

WHERE w.WordID = @FirstWordID         
  AND 
      @WordCount = 
                   (  
                   	  SELECT COUNT(*)
                   	  FROM dbo.DocWords AS ndw  -- выбираем следующие за 1ым искомым словом 
                   	  
                   	  JOIN @PassedWord AS pw 
                   	     ON 
                   	         pw.ind + w.WordInd = ndw.WordInd   
                   	     AND
                   	         pw.WordID =  ndw.WordID  
                   	     
                   	  WHERE 
                   				 ndw.DocID = w.DocID 
                   			 AND 
                   				 ndw.WordInd >= w.WordInd + 1 AND  ndw.WordInd <= w.WordInd + @WordCount  
                   			 AND 
                   			     pw.ind > 0 	                	                          	  
                                     	
                   )	    
 
GROUP BY w.DocID   -- группируем по документу 



Этот алгоритм можно оптимизировать, если хранить в словах общее число вхождений во все документы.
Т.е передали 3 слова, находим из них то, что встречалось меньше всех.
Ищем его вхождения, затем проверяем как в примере выше диапазон (от минус индекса мин слова до + (число слов - текущий индекс).
8 окт 12, 17:25    [13286166]     Ответить | Цитировать Сообщить модератору
 Re: Полнотекстовое индексирование вручную  [new]
Alan008
Member

Откуда: г. Иваново
Сообщений: 52
Спасибо, Леша777! Первый мыслящий человек! Теперь ждем вердикта от гуру по поводу recursive CTE (можно его применить или нет) :) Допустимо показать лишь сам подход, если указанные вопросы кажутся слишком сложными.
8 окт 12, 17:29    [13286182]     Ответить | Цитировать Сообщить модератору
 Re: Полнотекстовое индексирование вручную  [new]
--------------------------------
Guest
>>Запрос для 1) не очень сложный, я его уже придумал,

Скрипты заполнения тестовых таблиц,
текст 1 запроса

остальное - поможем
8 окт 12, 17:39    [13286262]     Ответить | Цитировать Сообщить модератору
 Re: Полнотекстовое индексирование вручную  [new]
Alan008
Member

Откуда: г. Иваново
Сообщений: 52
Выкладываю DDL:
+
CREATE TABLE [dbo].[WordsDict](
	[ID] [int] NOT NULL,
	[Value] [varchar](150) NOT NULL) ON [PRIMARY]
GO

INSERT INTO [dbo].[WordsDict]([ID], [Value])
VALUES (1,1), (2,2), (3,3)
GO

CREATE TABLE [dbo].[DocWords](
	[DocID] [int] NOT NULL,
	[WordID] [int] NOT NULL,
	[WordInd] [int] NOT NULL) ON [PRIMARY]
GO

INSERT INTO [dbo].[DocWords]([DocID], [WordID], [WordInd])
VALUES (1,1,1), (1,2,2), (2,3,1), (2,2,2)
GO


И текст запроса на отбор документов, содержащих, например, слова 1 и 2 (одновременно, в любом порядке)
+
SELECT [DocID] FROM [DocWords] 
WHERE [WordID] IN (1, 2)
GROUP BY [DocID]
HAVING Count(DISTINCT [WordID])=2 /* кол-во искомых слов - подставляется в запрос динамически*/
8 окт 12, 19:29    [13286890]     Ответить | Цитировать Сообщить модератору
 Re: Полнотекстовое индексирование вручную  [new]
Alan008
Member

Откуда: г. Иваново
Сообщений: 52
Ответов нет, сложную я всем задал задачку :)
Видимо, учесть очередность слов в одном SQL-запросе не получится, если использовать передачу ID'ов слов через IN (...), т.к. в этом случае в запрос не передается информация об очередности слов в исходном запросе.
Давайте предположим, что у меня есть некая функция, которая умеет трансформировать CSV-строку ID'ов слов в таблицу (WordID, WordInd):

SELECT ID, Ind
FROM word_ind_list('5,10,20')

WordID WordInd
5 1
10 2
20 3

Может ли кто-то составить запрос на получение списка документов, содержащих переданные слова строго в заданном порядке идущие подряд (при этом перечень слов передается в запрос не через IN, а через функцию word_ind_list)?
9 окт 12, 10:59    [13288780]     Ответить | Цитировать Сообщить модератору
 Re: Полнотекстовое индексирование вручную  [new]
tpg
Member

Откуда: Novosibirsk
Сообщений: 23902
Alan008
Ну начинается. Велосипед для поиска. Вы сделайте сначала такой велосипед, потом уж говорите, хорош он или плох. Для нечеткого поиска там используется стемминг в справочнике слов: кроме "исходного" варианта написания слова хранится усеченный вариант (основа) данного слова. К решению описанной выше проблемы это отношения не имеет, поэтому я не стал об этом писать.
ОФФ:
Делали.
Ничего особо сложного и интересного... Где-то даже в своем блоге на itcommunity.ru писал статью про аналогичный поиск, но проект закрыт и статью найти не могу )))
Погуглите по способам построения тех же интернет-поисковиков - всё везде одно и то же, отличия только в окружении "поискового ядра" - спайдеры там всякие и прочие новомодные штучки поиска по уже вводимым фразам.
Суть же самого ядра - это хэш функция и ранжирование - тут вам и четкий и нечеткий поиск - всё в одном флаконе.
10 окт 12, 06:44    [13293515]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить