Виртуальная таблица Spellfix1

1. Обзор

Эта виртуальная таблица spellfix1 может использоваться для поиска близких совпадений в большом словаре. Например, spellfix1 может использоваться для предложения исправлений к неверно написанным словам. Или она может использоваться с FTS4 для выполнения полнотекстового поиска, используя потенциально неправильно написанные слова.

Реализация виртуальной таблицы spellfix1 хранится в дереве исходного кода SQLite в папке дополнительных расширений, а именно в файле ext/misc/spellfix1.c. Виртуальная таблица spellfix1 не включена в склейку SQLite и не является частью стандартной сборки SQLite. Это загружаемое расширение.

После загрузки расширения spellfix1 создается экземпляр виртуальной таблицы spellfix1 так:

CREATE VIRTUAL TABLE demo USING spellfix1;

Термин "spellfix1" — это имя модуля spellfix и должен быть введён как показано. Термин "demo" — это имя виртуальной таблицы, которую вы будете создавать, и его можно изменить, чтобы удовлетворить потребности вашего приложения. Виртуальная таблица изначально пуста. Для того, чтобы виртуальная таблица была полезной, вам нужно заполнить её своим словарем. Предположим, у вас есть список слов в таблице под названием "big_vocabulary". Тогда сделайте так:

INSERT INTO demo(word) SELECT word FROM big_vocabulary;

Если вы собираетесь использовать эту виртуальную таблицу в сотрудничестве с таблицей FTS4 (для исправления правописания поисковых запросов), то вы можете извлечь словарь, используя таблицу fts4aux:

INSERT INTO demo(word) SELECT term FROM search_aux WHERE col='*';

Вы также можете предоставить виртуальной таблице "ранг" для каждого слова. "Ранг" — это оценка частоты слова. Более высокие числа означают, что слово более частое. Если вы опустите ранг при заполнении таблицы, то предполагается ранг 1. Но если у вас есть информация о ранге, вы можете её предоставить, и виртуальная таблица будет немного предпочитать выбор более часто используемых терминов. Чтобы заполнить ранг из таблицы fts4aux "search_aux", сделайте что-то вроде этого:

INSERT INTO demo(word,rank)
   SELECT term, documents FROM search_aux WHERE col='*';

Чтобы запросить виртуальную таблицу, включите оператор MATCH в условие WHERE. Например:

SELECT word FROM demo WHERE word MATCH 'kennasaw';

Используя набор данных американских географических названий (полученный из http://geonames.usgs.gov/domestic/download_data.htm), вышеприведённый запрос возвращает 20 результатов, начиная с:

kennesaw
kenosha
kenesaw
kenaga
keanak

Если вы добавите символ '*' в конец шаблона, то выполняется поиск по префиксу. Например:

SELECT word FROM demo WHERE word MATCH 'kennes*';

Возвращает 20 результатов, начинающихся с:

kennesaw
kennestone
kenneson
kenneys
keanes
keenes

2. Уточнения поиска

По умолчанию таблица spellfix1 возвращает не более 20 результатов. (Она может вернуть меньше 20, если было меньше хороших совпадений.) Вы можете изменить верхнюю границу количества возвращаемых строк, добавив термин "top=N" в условие WHERE вашего запроса, где N — новое максимальное значение. Например, чтобы увидеть 5 лучших совпадений:

SELECT word FROM demo WHERE word MATCH 'kennes*' AND top=5;

Каждая запись в виртуальной таблице spellfix1 связана с конкретным языком, определяемым целым числом "langid". Значение langid по умолчанию — 0, и если не выполняются другие действия, весь словарь является частью языка 0. Но если вашему приложению нужно работать с несколькими языками, вы можете указать различные элементы словаря для каждого языка, указав поле langid при заполнении таблицы. Например:

INSERT INTO demo(word,langid) SELECT word, 0 FROM en_vocabulary;
INSERT INTO demo(word,langid) SELECT word, 1 FROM de_vocabulary;
INSERT INTO demo(word,langid) SELECT word, 2 FROM fr_vocabulary;
INSERT INTO demo(word,langid) SELECT word, 3 FROM ru_vocabulary;
INSERT INTO demo(word,langid) SELECT word, 4 FROM cn_vocabulary;

После того, как виртуальная таблица была заполнена элементами из нескольких языков, укажите интересующий язык, используя термин "langid=N" в условии WHERE запроса:

SELECT word FROM demo WHERE word MATCH 'hildes*' AND langid=1;

Обратите внимание, что если вы не включаете термин "langid=N" в условие WHERE, поиск будет производиться по языку 0 (английский в примере выше). Все поиски spellfix1 выполняются для одного идентификатора языка. Нет возможности искать по всем языкам одновременно.

3. Подробности виртуальной таблицы

В каждой строке виртуальной таблицы spellfix1 есть уникальный rowid с семью столбцами плюс пять скрытых дополнительных столбцов. Столбцы следующие:

rowid

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

word

Текст слова, соответствующего шаблону. И слово, и шаблон могут содержать символы Юникода и могут быть смешанного регистра.

rank

Это ранг слова, как указано в исходном операторе INSERT.

distance

Это расстояние редактирования или расстояние Левенштейна от шаблона до слова.

langid

Это идентификатор языка слова. Все запросы выполняются для одного идентификатора языка, который по умолчанию равен 0. Для любого данного запроса это значение одинаково для всех строк.

score

Счёт — это комбинация ранга и расстояния. Идея в том, что меньший счёт лучше. Виртуальная таблица пытается найти слова с наименьшим счётом и по умолчанию (если не указано ORDER BY) возвращает результаты в порядке возрастания счёта.

matchlen

При поиске по префиксу matchlen — это количество символов в строке, которые совпадают с префиксом. Для поиска, не являющегося поиском по префиксу, это то же самое, что length(word).

phonehash

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

top

(СКРЫТО) Для любого запроса это значение одинаково для всех строк. Это целое число, которое является максимальным количеством строк, которые будут выведены. Фактическое количество выведенных строк может быть меньше этого числа, но никогда не будет больше. Значение top по умолчанию равно 20, но это можно изменить для каждого запроса, включив термин вида "top=N" в условие WHERE запроса.

scope

(СКРЫТО) Для любого запроса это значение одинаково для всех строк. Scope — это мера того, насколько широко виртуальная таблица ищет соответствующие слова. Меньшие значения scope вызывают более широкий поиск. Scope обычно выбирается автоматически и ограничен значением 4. Приложения могут изменить scope, включив термин вида "scope=N" в условие WHERE запроса. Увеличение scope сделает запрос быстрее, но уменьшит возможные исправления.

srchcnt

(СКРЫТО) Для любого запроса это значение одинаково для всех строк. Это целое число, которое является количеством слов, проверенных с помощью алгоритма расстояния редактирования, чтобы найти лучшие совпадения, которые в конечном итоге отображаются. Это значение предназначено только для диагностики.

soundslike

(СКРЫТО) При вставке записей словаря это поле можно установить в соответствие с тем, как слово звучит. Подробности см. в разделе ОБРАБОТКА НЕОБЫЧНЫХ И СЛОЖНЫХ НАПИСАНИЙ ниже.

command

(СКРЫТО) Значение столбца "command" всегда NULL. Однако приложения могут вставлять специальные строки в столбец "command", чтобы вызвать определённые действия в виртуальной таблице spellfix1. Например, вставка строки 'reset' в столбец "command" заставит виртуальную таблицу перечитать свои весы расстояния редактирования (если они есть).

4. Алгоритм

Виртуальная таблица spellfix1 создает единственную теневую таблицу под названием "%_vocab" (где % заменяется именем виртуальной таблицы; Например, "demo_vocab" для виртуальной таблицы "demo"). Теневая таблица содержит следующие столбцы:

id

Уникальный идентификатор (INTEGER PRIMARY KEY).

rank

Ранг слова.

langid

Идентификатор языка для этой записи.

word

Исходный текстовый элемент словаря UTF8.

k1

Слово, транслитерированное в строчные буквы ASCII. Существует стандартная таблица сопоставлений символов, не являющихся ASCII, с ASCII. Примеры: "æ" -> "ae", "þ" -> "th", "ß" -> "ss", "á" -> "a", ... Вспомогательная функция spellfix1_translit(X) выполнит преобразование символов, не являющихся ASCII, в ASCII. Встроенная функция lower(X) преобразует в строчные буквы. Таким образом: k1 = lower(spellfix1_translit(word)). Если слово уже полностью в строчных буквах ASCII, то столбец k1 будет содержать NULL. Это уменьшает требования к хранению для таблицы %_vocab и помогает spellfix работать немного быстрее. Поэтому целесообразно заполнять как можно большую часть таблицы spellfix с использованием словаря в нижнем регистре ASCII.

k2

Это поле содержит фонетический код, полученный из coalesce(k1,word). Буквы, имеющие похожие звуки, отображаются в один символ. Например, все гласные и гласные кластеры преобразуются в один символ "A". А буквы "p", "b", "f" и "v" все преобразуются в "B". Все носовые звуки представляются как "N" и так далее. Преобразование основано на идеях, найденных в системах фонетического соответствия Soundex, Metaphone и других проверенных систем. Этот ключ может быть сгенерирован функцией spellfix1_phonehash(X). Следовательно: k2 = spellfix1_phonehash(coalesce(k1,word)).

Также существует функция для вычисления расстояния редактирования Вагнера или расстояния Левенштейна между шаблоном и словом. Эта функция представлена как spellfix1_editdist(X,Y). Функция расстояния редактирования возвращает "стоимость" преобразования X в Y. Некоторые преобразования стоят больше, чем другие. Изменение одной гласной на другую гласную, например, относительно дешево, как и удвоение константы или пропуск второго символа двойной константы. Другие преобразования более затратны. Идея в том, что функция расстояния редактирования возвращает низкую стоимость для похожих слов и более высокую стоимость для слов, которые дальше друг от друга. В этой реализации максимальная стоимость любого редактирования одного символа (удаление, вставка или замена) составляет 100, причём для некоторых редактирований (например, преобразования гласных) используются более низкие стоимости.

«Счёт» для сравнения — это расстояние редактирования между шаблоном и словом, скорректированное вниз на основе двоичного логарифма ранга слова. Например, совпадение с расстоянием 100, но рангом 1000, будет иметь счёт 122 (= 100 - log2(1000) + 32), в то время как совпадение с расстоянием 100 и рангом 1 будет иметь счёт 131 (100 - log2(1) + 32). (Примечание: к каждому счёту добавляется константа 32, чтобы он не стал отрицательным в случае, если расстояние редактирования равно нулю.) Таким образом, часто используемые слова получают несколько меньшую стоимость, что способствует их перемещению к вершине списка альтернативных написаний.

Простое реализация орфографического корректора заключалась бы в сравнении поискового запроса со всеми словами в словаре и выборе 20 с наименьшими счётами. Однако, как правило, в словаре будет сотни тысяч или миллионы слов, и поэтому этот подход недостаточно быстрый.

Предположим, что слово, которое исправляется орфографически, — это X. Чтобы ограничить область поиска, X преобразуется в ключ типа k2 с помощью эквивалента:

   key = spellfix1_phonehash(lower(spellfix1_translit(X)))

Этот ключ затем ограничивается «объёмом» символов. Значение по умолчанию для объёма — 4, но альтернативное значение объёма можно указать, используя термин «scope=N» в предложении WHERE. После того, как ключ был усечён, расстояние редактирования рассчитывается для каждого термина в словаре, у которого значение k2 начинается с усечённого ключа.

Например, предположим, что входное слово — «Paskagula». Фонетический ключ — «BACACALA», который затем усекается до 4 символов «BACA». Затем расстояние редактирования рассчитывается для 4980 записей (из общего числа 272 597 записей) словаря, значения k2 которых начинаются с BACA, что даёт «Pascagoula» в качестве лучшего совпадения.

Ищутся только термины словаря с совпадающим langid. Таким образом, одна и та же таблица может содержать записи из нескольких языков, и будет использоваться только запрашиваемый язык. Значение langid по умолчанию — 0.

5. Настраиваемое Расстояние Редактирования

Встроенную функцию расчета расстояния редактирования Вагнера с фиксированными весами можно заменить функцией editdist3() расчета расстояния редактирования с весами, определяемыми приложением, и поддержкой юникода, указав параметр «edit_cost_table=TABLENAME» для модуля spellfix1 при создании виртуальной таблицы. Например:

CREATE VIRTUAL TABLE demo2 USING spellfix1(edit_cost_table=APPCOST);

Функцию editdist3() расчета расстояния редактирования также можно выбрать или отключить во время выполнения, вставив соответствующую строку в столбец «command» виртуальной таблицы:

INSERT INTO demo2(command) VALUES('edit_cost_table=APPCOST');

В приведённых примерах таблица APPCOST будет использована для поиска коэффициентов расстояния редактирования. Именно наличие параметра «edit_cost_table=» в имени модуля spellfix1 вызывает использование функции editdist3() вместо встроенной функции расчёта расстояния редактирования. Если APPCOST — пустая строка, используется встроенная функция расчета расстояния редактирования Вагнера.

Коэффициенты расстояния редактирования обычно считываются из таблицы APPCOST один раз и после этого хранятся в памяти. Следовательно, изменения в таблице APPCOST во время выполнения обычно не повлияют на результаты расчета расстояния редактирования. Однако, вставка специальной строки «reset» в столбец «command» виртуальной таблицы приводит к повторному считыванию коэффициентов расстояния редактирования из таблицы APPCOST. Таким образом, приложения должны выполнять SQL-запрос, аналогичный следующему, при возникновении изменений в таблице APPCOST:

INSERT INTO demo2(command) VALUES("reset");

6. Обработка Необычных и Сложных Написаний

Приведённый выше алгоритм работает довольно хорошо в большинстве случаев, но есть исключения. Эти исключения могут быть обработаны путём добавления дополнительных записей в виртуальную таблицу с использованием столбца «soundslike».

Например, многие слова греческого происхождения начинаются с букв «ps», где «p» не произносится. Примеры: psalm, pseudonym, psoriasis, psyche. В другом примере, многие шотландские фамилии могут быть написаны с начальными «Mac» или «Mc». Таким образом, «MacKay» и «McKay» произносятся одинаково.

Можно адаптироваться к словам, которые не пишутся так, как произносятся, добавив дополнительные записи в виртуальную таблицу для того же слова, но с альтернативным написанием в столбце «soundslike». Например, каноническая запись для «psalm» будет такой:

  INSERT INTO demo(word) VALUES('psalm');

Чтобы улучшить возможность исправления написания «salm» на «psalm», добавьте запись, подобную этой:

  INSERT INTO demo(word,soundslike) VALUES('psalm','salm');

Можно добавлять несколько записей для одного слова, при условии, что каждое имеет уникальное значение «soundslike». Обратите внимание, что если значение «soundslike» не указано, оно по умолчанию устанавливается равным самому слову.

Ниже приведены некоторые случаи, когда может иметь смысл добавить дополнительные записи «soundslike». Конкретные записи будут зависеть от приложения и целевого языка.

• Непроизносимое «p» в словах, начинающихся с «ps»: psalm, psyche
• Непроизносимое «p» в словах, начинающихся с «pn»: pneumonia, pneumatic
• Непроизносимое «p» в словах, начинающихся с «pt»: pterodactyl, ptolemaic
• Непроизносимое «d» в словах, начинающихся с «dj»: djinn, Djikarta
• Непроизносимое «k» в словах, начинающихся с «kn»: knight, Knuthson
• Непроизносимое «g» в словах, начинающихся с «gn»: gnarly, gnome, gnat
• «Mac» против «Mc» в начале шотландских фамилий
• Звуки «Tch» в словах славянского происхождения: Tchaikovsky против Chaykovsky
• Буква «j», произносимая как «h» в испанском языке: LaJolla
• Слова, начинающиеся с «wr» против «r»: write против rite
• Разнообразные проблемные слова, такие как «debt», «tsetse», «Nguyen», «Van Nuyes».

7. Вспомогательные Функции

Модуль исходного кода, реализующий виртуальную таблицу spellfix1, также реализует несколько SQL-функций, которые могут быть полезны приложениям, использующим spellfix1, или для тестирования или диагностики при разработке приложений, использующих spellfix1. Доступны следующие вспомогательные функции:

editdist3(P,W)
editdist3(P,W,L)
editdist3(T)

Эти функции обеспечивают прямой доступ к версии функции расчета расстояния редактирования Вагнера, которая позволяет задавать весы для операций редактирования. Первые две формы этой функции сравнивают шаблон P со словом W и возвращают расстояние редактирования. В первой функции предполагается langid=0, а во второй langid задаётся параметром L. Третья форма этой функции перезагружает коэффициенты расстояния редактирования из таблицы с именем T.

spellfix1_editdist(P,W)

Эта функция предоставляет доступ к встроенной функции расчета расстояния редактирования Вагнера, использующей стандартные фиксированные затраты. Возвращаемое значение — расстояние редактирования, необходимое для преобразования W в P.

spellfix1_phonehash(X)

Эта функция строит фонетический хеш чистого ascii-входного слова X и возвращает этот хеш. Эта функция используется внутри spellfix1 для преобразования столбца K1 таблицы-тени в столбец K2.

spellfix1_scriptcode(X)

Принимая на вход строку X, эта функция пытается определить доминирующий шрифт и возвращает числовой код этого шрифта по ISO-15924. Текущая реализация понимает следующие шрифты:

• 215 - Латинский
• 220 - Кириллический
• 200 - Греческий

В будущих версиях могут быть добавлены дополнительные языковые коды.

spellfix1_translit(X)

Эта функция транслитерирует текст юникода в чистый ascii, возвращая чистое ascii-представление входного текста X. Эта функция используется внутри spellfix1 для преобразования слов словаря в столбец K1 таблицы-тени.

8. Функция editdist3

Алгоритм editdist3 — это функция, которая вычисляет минимальное расстояние редактирования (также известное как расстояние Левенштейна) между двумя входными строками. Алгоритм editdist3 — это настраиваемая альтернатива функции расчета расстояния редактирования по умолчанию для spellfix1. Функции editdist3 включают:

• Она работает с текстом юникода (UTF8).

• Приложение может предоставить таблицу с затратами на вставки, удаления и замены.

• В таблице затрат можно перечислить вставки, удаления и замены нескольких символов.

9. Таблица затрат editdist3

Для программирования затрат editdist3 создайте таблицу, подобную следующей:

CREATE TABLE editcost(
  iLang INT,   -- The language ID
  cFrom TEXT,  -- Convert text from this
  cTo   TEXT,  -- Convert text into this
  iCost INT    -- The cost of doing the conversion
);

Таблица затрат может иметь любое имя — она не должна называться «editcost». И таблица может содержать дополнительные столбцы. Единственное требование состоит в том, что таблица должна содержать четыре указанных столбца с точным указанием имён.

Столбец iLang — это целое число без знака, которое определяет набор затрат, подходящих для конкретного языка. Функция editdist3 будет использовать только одно значение iLang для любого вычисления расстояния редактирования. Значение по умолчанию — 0. Рекомендуется приложениям, которые нуждаются только в использовании одного языка, всегда использовать iLang==0 для всех записей.

Столбец iCost — это числовая стоимость преобразования cFrom в cTo. Это значение должно быть целым числом без знака и, вероятно, меньше 100. Стандартные затраты на вставку и удаление одного символа составляют 100, а стандартные затраты на замену одного символа на другой — 150. Стоимость 10000 или более считается «бесконечной» и приводит к игнорированию правила.

Столбцы cFrom и cTo показывают строки преобразования редактирования. Один или оба столбца могут содержать более одного символа. Или любой столбец (но не оба) может содержать пустую строку. Когда cFrom пуста, это стоимость вставки cTo. Когда cTo пуста, это стоимость удаления cFrom.

В алгоритме spellfix1, cFrom — это текст, введённый пользователем, а cTo — правильно написанный текст, как он существует в базе данных. Цель алгоритма editdist3 — определить, насколько близок текст, введённый пользователем, к тексту словаря.

В таблице затрат есть три записи для специальных случаев:

Если любая из вышеперечисленных записей для специальных случаев отсутствует, то используется значение 100 для вставки и удаления и 150 для замены. Чтобы отключить стандартные вставку, удаление и/или замену, установите их соответствующие затраты на 10000 или более.

Другие записи в таблице затрат описывают преобразования для конкретных символов. Затраты на конкретные преобразования должны быть меньше, чем стандартные затраты, в противном случае стандартные затраты будут иметь приоритет, и конкретные преобразования никогда не будут использоваться.

Пример записи в таблице затрат:

INSERT INTO editcost(iLang, cFrom, cTo, iCost)
VALUES(0, 'a', 'ä', 5);

Это правило говорит о том, что буква «a» на входе пользователя может соответствовать букве «ä» в словаре с штрафом 5.

INSERT INTO editcost(iLang, cFrom, cTo, iCost)
VALUES(0, 'ss', 'ß', 8);

Число символов в cFrom и cTo не обязательно должно быть одинаковым. Это правило говорит о том, что «ss» на входе пользователя будет соответствовать «ß» с штрафом 8.

10. Экспериментирование с функцией editcost3()

Виртуальная таблица spellfix1 использует editdist3, если параметр «edit_cost_table=TABLE» указан в качестве аргумента при создании виртуальной таблицы spellfix1. Но editdist3 также можно протестировать напрямую с помощью встроенной SQL-функции «editdist3()». SQL-функция editdist3() имеет 3 формы:

1. editdist3('TABLENAME');
2. editdist3('string1', 'string2');
3. editdist3('string1', 'string2', langid);

В первой форме коэффициенты редактирования расстояния загружаются из таблицы с именем 'TABLENAME'. Любые предыдущие коэффициенты отбрасываются. Таким образом, при экспериментировании с весами и изменении таблицы весов достаточно повторно выполнить одноаргументную форму editdist3(), чтобы перезагрузить изменённые коэффициенты. Обратите внимание, что веса редактирования расстояния, используемые SQL-функцией editdist3(), независимы от весов, используемых виртуальной таблицей spellfix1.

Вторая и третья формы возвращают вычисленное расстояние редактирования между строками 'string1' и 'string2'. Во второй форме используется идентификатор языка 0. Идентификатор языка задаётся в третьей форме.

Эта страница была последним обновлена 10.10.2023 17:29:48 UTC