Сделать полнотекстовый поиск управляемым и удобным

Необходимы перепосты и переводы на другие языки. Газета "Компьютерные вести" kv.by/index2010213801.htm Издание 2-е, исправленное. Другие статьи (оглавление)

Когда мы набираем в Google или Yandex, к примеру, "Чань-буддизм иерархия язык", то вместе со ссылками получаем некоторый комментарий, например, "Иерархия деструктивных средств чань-буддийского языка", в комментарии сервер выделяет слова, которые нашел. Конечно, сервер не ищет в интернете - он ищет в своей базе данных. Но запросы в базу с выделением найденного нужны не только ему, но и нам, обычным пользователям. Роль "случайных" пользователей СУБД с каждым днем все возрастает, фактически мы составляем уже большинство. А простому смертному реализовать такое крайне сложно. В коммерческих СУБД не воплощают, а в бесплатных несут такую околесицу, что с нормальными когнитивными способностями и применить невозможно, см. например неудачную попытку в Postgres. Воистину очень печально отсутствие в каких-либо намерений по поддержке работы не-программистов. Конечно, совсем нелегко найти простой и элегантный синтаксис для того, чтобы указать сколько слов до и после найденных надо вывести, какими тегами обрамлять найденные слова, в т.ч. в зависимости от того, в какой части строки они найдены, какие и сколько вариантов перестановок найденных слов выводить. Однако автор хотел бы предпринять такую попытку и услышать комментарии общественности, насколько ему это удалось. Несколько слайдов, иллюстрирующих идеи, вы можете видеть в sql5.19.3.pdf на с.188-194. Предложения дополняют статью "Систематика и обобщение методологий моделирования и языков программирования"

Вложенные поля

Пусть у нас есть таблица 's' с полями 'pk' (в ней первичный ключ), 's1' и 's2', единственная запись которой содержит

1, 10, "In the morning, dog comes, cat comes home too. Continue in the NEXT issue."

Вообразим, что строка разбита на слова, а слова хранятся в некоторой таблице с колонками @TOKEN (само слово),@SN (порядковый номер слова в поле), @BEGINNING (смещение первой буквы слова), @END (смещение последней буквы слова).

@TOKEN	@SN	@BEGINNING	@END
In	1	1	2
the	2	4	6
morning	3	8	14
dog	4	17	19
comes	5	21	24
cat	6	27	29
comes	7	31	34
home	8	36	39
too	9	41	43
Continue	10	46	53
in	11	55	56
the	12	58	60
NEXT	13	62	65
issue	14	67	71

Пусть эта таблица вложена в текстовое поле 's2' (мы такое вообразим, т.е. это nested table), и мы синтаксически имеем доступ к этим колонкам как к s2.@TOKEN, s2.@SN, s2.@BEGINNING, s2.@END. Будем называть их вложенными колонками (nested columns). Упоминание их после WHERE позволяет гибко формулировать условия для полнотекстового поиска. Т.е. в подзапросах они ведут себя как колонки, но во внешний мир СУБД возвращает их как обычное поле под именем 's2', образованное агрегатом конкатенации, прошедшимся по вложенной колонке. Это позволяет автоматически видеть результаты поиска как текстовую строку. Например, вывод поля s2.@SN возвращает строку, состоящую из порядковых номеров найденных слов, а не из самих слов; поля s2.@BEGINNING - из смещений первых букв слов, s2.@END - из смещений последних букв слов. При конкатенации гарантируется, что

порядок слов остается неизменным (т.е. 'ORDER BY s2.@SN' писать не надо)
все знаки препинания, присутствовавшие между теми из найденных слов, которые были соседями в исходной строке, попадают в результат запроса
найденные слова, которые не были соседями, разделяются значением переменной среды OMITTED_MEDIATE (поисковые сервера обычно изображают многоточием перерывы в цитировании); к началу и концу возвращаемой строки добавляется также содержимое OMITTED_FIRST и OMITTED_LAST, если для её получения пришлось в исходной строке отбросить начальные или конечные слова

Чтобы обрамить то, что пожелаем, тегами-константами, операции с вложенными колонками обладают следующими свойствами

любая функция вложенной колонки и не-вложенного поля любой таблицы либо вложенной колонки и константы

дает новую таблицу, вложенную в ту же самую родительскую
даже если в новой вложенной таблице вы не сформировали в явном виде @SN, то неявно такая колонка всегда присутствует
порядок следования в ней повторяет порядок следования в исходной вложенной таблице
и задает порядок конкатенации при выводе во внешний мир

конкатенация не текстовых полей, а их вложенных колонок

есть UNION для вложенных колонок
@SN всегда неявно присутствует в результате UNION
если два значения в ней равны, то сначала следует значение из левого операнда конкатенации, потом из правого

Для полноты картины отметим также вопрос, остающийся за пределами настоящей статьи, а именно возможность изменять текстовые поля с помощью SQL, не прибегая в СУБД к громаде строковых функций, например

'INSERT INTO s (s2.@TOKEN, s2.@SN) VALUES ("new", 15)' вставляет новую запись, причем если её s2.@SN совпадает с уже содержащимся во вложенной таблице, то сначала располагается новая запись, затем старая ("вставка перед")
'UPDATE s SET s2.@TOKEN = ""+s2.@TOKEN+"" ', а также 'DELETE FROM s WHERE s2.@BEGINNING >= 100' не обладают никакими новыми свойствами. Для замены, например, трех слов на другие четыре, нужны DELETE и INSERT, а не UPDATE
после каждой операции значения @SN, @BEGINNING, @END во всей вложенной таблице обновляются

Несколько совпадений

Даже в одной строке может быть найдено несколько образцов, а значит каждая запись может быть возвращена несколько раз: будем называть этот процесс размножением (propagation), а записи, порожденные из одной - порожденной группой (propagated group). Чтобы в клиентской программе выбрать конкретный экземпляр группы, СУБД автоматически добавляет целочисленное поле SYS_CLUE, содержащее уникальный идентификатор записи внутри группы. В разных группах поле может содержать одинаковые значения, неоднозначность разрешает первичный ключ записей. Например, запрос слов из множества "comes next", который выводит найденные, а также и по одному слову слева и справа от них

SELECT s1, s2.@TOKEN
FROM   s
WHERE  s2.@SN IN (
  SELECT s2.@SN
  FROM   s, (
    SELECT s2.@SN AS fn
    FROM   s
    WHERE  s2.@TOKEN IN "comes next"
            )
  WHERE  ABS(s2.@SN-fn) <= 1
                 );

находит два образца и возвращает две записи (для строки "comes next" автоматически генерируется её вложенная таблица как только строка введена в СУБД, эту вложенную таблицу и использует оператор IN)

s1	s2	SYS_CLUE
10	dog comes, cat ... the NEXT issue	1
10	cat comes home ... the NEXT issue	2

Можно указать перестановку слов с помощью 'WHERE s2.@TOKEN =~ "come next" ' (подробнее о перестановке на с.180-183 вышеупомянутого pdf-документа), в т.ч. с ограничением количества перестановок 'WHERE s2.@TOKEN TO "come next" PERMUTATIONS <=2', результаты всегда выдаются, начиная с наименьшего количества перестановок, в направлении возрастания количества.

И опять же для полноты картины определимся, что комбинация полнотекстовых поисков обладает следующими свойствами

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

Обрамление тегами

Чтобы в момент вывода слов во внешний мир проводить с ними различные операции, в т.ч. чтобы обрамлять разными тегами, достаточно давать алиасы аргументам функций. Тогда например, запрос, возвращающий найденные слова обрамленными тегами и , по одному слову слева и справа от них - тегами и , а все остальные слова между найденными без обрамления, выглядит как показано ниже. Чтобы читателю легче было визуально сгруппировать @TOKEN, относящиеся к разным подзапросам, автор выделил некоторые из них строчными буквами; а также для удобства чтения перенес DISTINCT от нескольких аргументов под WHERE - таков уж был убогий синтаксис современных СУБД. DISTINCT нужен ввиду декартового произведения колонок '@sn' (соответствующих @token) и 'fn'.

SELECT s1, ("<b>" +s2.@TOKEN AS f1 +"</b>" ) +
           ("<em>"+s2.@TOKEN AS f2 +"</em>") +
           (       s2.@TOKEN AS f3         ) 
FROM   s
WHERE  f1 IN "comes next"
  AND  f2 IN (
            SELECT s2.@token
            FROM   s, (
              SELECT s2.@SN AS fn
              FROM   s
              WHERE  s2.@TOKEN IN "comes next"
                      )
            WHERE  ABS(s2.@sn-fn)=1
              AND  DISTINCT(s2.@token, s2.@sn)
             )
  AND  f3 BETWEEN             
            SELECT MIN(s2.@SN)
            FROM   s
            WHERE  s2.@TOKEN IN "comes next"
          AND
            SELECT MAX(s2.@SN)
            FROM   s
            WHERE  s2.@TOKEN IN "comes next"
  AND  f3 NOT IN ( -- not in <em>, i.e. not f2
            SELECT s2.@token
            FROM   s, (
              SELECT s2.@SN AS fn
              FROM   s
              WHERE  s2.@TOKEN IN "comes next"
                      )
            WHERE  ABS(s2.@sn-fn)=1
              AND  DISTINCT(s2.@token, s2.@sn)
                 );

Этот запрос возвращает следующий результат

s1	s2	SYS_CLUE
10	<em>dog</em> <b>comes</b>, <em>cat</em> comes home too. Continue in <em>the</em> <b>NEXT</b> <em>issue</em>	1
10	<em>cat</em> <b>comes</b> <em>home</em> too. Continue in <em>the</em> <b>NEXT</b> <em>issue</em>	2

Индексация

Для индексации нужна прежде всего некоторая таблица 'delimiters' из двух полей, первое содержит первичный ключ, второе - знаки-разделители: пробел, табуляцию, возврат каретки, переход на новую строку, все знаки пунктуации. Кроме того, если нужно рассматривать все грамматические формы одного слова как одну лексему, то нужна таблица, группирующая грамматические формы. Например, как это сделано в таблице 'tokens'. В её первые два поля удобно заносить командой 'TOKENIZE s(s2) INTO tokens DELIMITING delimiters [, delimiters2]', а во второе и третье - стандартной командой заполнения таблицы из файла 'COPY tokens( idlexeme, token ) FROM c:/lexeme.txt'.

**tokens**
idtoken	token	idlexeme
1	in	1
2	the	2
3	morning	3
4	dog	4
5	comes	5
12	come	5
6	cat	6
7	home	7
8	too	8
9	continue	9
10	next	10
11	issue	11

Далее, нам нужна некоторая таблица типа 'items', поле 'idtoken' которой ссылается внешним ключем на одноименное поле таблицы 'tokens', и в поля 'idfield', 'pk', 'sn', 'beginning', 'end' которой скопированы: идентификатор поля 's2', взятый из системных таблиц, описывающих схему базы данных; первичный ключ таблицы 's'; поля @SN, @BEGINNING, @END таблицы, вложенной в поле 's2'. Поля 'own name' и 'abbreviation' указывают, является ли слово именем собственным или аббревиатурой. Поле 'idfield' нужно, чтобы командой 'SELECT ... FROM items' искать сразу во многих таблицах базы данных. Разложение поля 's2' сразу всех записей будем производить командой 'ITEMIZE s(s2) INTO items DELIMITING delimiters [, delimiters2] TOKENIZING tokens'.

**items**
idfield	pk	idtoken	own name	abbreviation	sn	beginning	end
505	1	1	yes		1	1	2
505	1	1			11	55	56
505	1	2			2	4	6
505	1	2			12	58	60
505	1	3			3	8	14
505	1	4			4	17	19
505	1	5			5	21	24
505	1	5			7	31	34
505	1	6			6	27	29
505	1	7			8	36	39
505	1	8			9	41	43
505	1	9	yes		10	46	53
505	1	10		yes	13	62	65
505	1	11			14	67	71

Теперь индексирование представляет собой стандартную команду CREATE INDEX для таблиц 'tokens' и 'items'. Все эти индексы автоматически удаляются при удалении любой из таблиц 'delimiters', 'tokens', 'items'. Может понадобиться отключать одни 'items' и подключать к полнотекстовому поиску другие 'items' - будем делать это с помощью 'SET NOMENCLARURE items [, items2]'. Параметр NOMENCLARURE является сессионным, т.е. два одновременных соединения одного и того же пользователя с СУБД могут иметь различные значения этого параметра.

Если 'tokens' не содержит некоторых слов или их форм, то сам факт наличия индексов переключает поиск по всем словам или формам на поиск только по проиндексированным. Т.е. не только увеличивается скорость поиска, но и может сужаться диапазон слов, по которым поиск производится. Чтобы одновременно по оставшимся словам произвести не-индексированный поиск, будем указывать квантор ALL перед названием вложенной колонки 'SELECT s1, ALL s2.@TOKEN FROM s'. Команда TOKENIZE добавляет во вложенной таблице колонки 's2.@IDTOKEN', 's2.@IDFIELD', а команда ITEMIZE - колонку 's2.@IDLEXEME'. Этими тремя новыми колонками также можно пользоваться в запросах.

Дмитрий Тюрин (DmitryTurin.narod.ru):
dima.turin@centrum.cz (все письма из домена .ru попадают в спам), dima.turin@gmail.com

idfield	pk	idtoken	own name	abbreviation	sn	beginning	end
505	1	1	yes		1	1	2
505	1	1			11	55	56
505	1	2			2	4	6
505	1	2			12	58	60
505	1	3			3	8	14
505	1	4			4	17	19
505	1	5			5	21	24
505	1	5			7	31	34
505	1	6			6	27	29
505	1	7			8	36	39
505	1	8			9	41	43
505	1	9	yes		10	46	53
505	1	10		yes	13	62	65
505	1	11			14	67	71

idfield	pk	idtoken	own name	abbreviation	sn	beginning	end
505	1	1	yes		1	1	2
505	1	1			11	55	56
505	1	2			2	4	6
505	1	2			12	58	60
505	1	3			3	8	14
505	1	4			4	17	19
505	1	5			5	21	24
505	1	5			7	31	34
505	1	6			6	27	29
505	1	7			8	36	39
505	1	8			9	41	43
505	1	9	yes		10	46	53
505	1	10		yes	13	62	65
505	1	11			14	67	71

idfield	pk	idtoken	own name	abbreviation	sn	beginning	end
505	1	1	yes		1	1	2
505	1	1			11	55	56
505	1	2			2	4	6
505	1	2			12	58	60
505	1	3			3	8	14
505	1	4			4	17	19
505	1	5			5	21	24
505	1	5			7	31	34
505	1	6			6	27	29
505	1	7			8	36	39
505	1	8			9	41	43
505	1	9	yes		10	46	53
505	1	10		yes	13	62	65
505	1	11			14	67	71