Виртуальная таблица 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, если подходящих совпадений окажется меньше.) Изменить верхнюю границу числа возвращаемых строк можно, добавив в предложение WHERE запроса термин "top=N", где 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

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

rank

Ранг слова, заданный в исходной инструкции INSERT.

distance

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

langid

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

score

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

matchlen

При поиске по префиксу matchlen — это число символов в строке, совпадающих с префиксом. При поиске без префикса это значение совпадает с length(word).

phonehash

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

top

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

scope

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

srchcnt

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

soundslike

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

command

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

4. Алгоритм

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

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; некоторые изменения (например, преобразование гласных) имеют меньшую стоимость.

"Оценка" сравнения — это расстояние редактирования между шаблоном и словом, уменьшенное на логарифм ранга слова по основанию 2. Например, совпадение с расстоянием 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)))

Затем этот ключ ограничивается "scope" символами. Значение scope по умолчанию равно 4, но альтернативное значение можно указать с помощью термина "scope=N" в предложении WHERE. После усечения ключа расстояние редактирования вычисляется для каждого термина словаря, значение k2 которого начинается с сокращённого ключа.

Например, пусть входное слово — "Paskagula". Его фонетический ключ — "BACACALA", который затем усекается до четырёх символов: "BACA". После этого расстояние редактирования вычисляется для 4980 записей из общего числа 272 597, значения k2 которых начинаются с BACA. Лучшим совпадением оказывается "Pascagoula".

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

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

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

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. Поэтому при изменении таблицы APPCOST приложениям следует выполнить SQL-инструкцию, подобную следующей:

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, а также при тестировании и диагностике во время разработки таких приложений. Доступны следующие вспомогательные функции:

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)

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

spellfix1_scriptcode(X)

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

• 215 — латиница
• 220 — кириллица
• 200 — греческое письмо

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

spellfix1_translit(X)

Эта подпрограмма транслитерирует текст Unicode в символы ASCII и возвращает ASCII-представление входного текста X. Эта функция используется внутри для преобразования слов словаря в столбец K1 теневой таблицы.

8. Функция editdist3

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

• Поддерживает текст Unicode (UTF8).

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

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

9. Таблица COST для 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". Но editdist3 также можно напрямую протестировать с помощью встроенной SQL-функции "editdist3()". SQL-функция editdist3() имеет три формы:

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

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

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

Последнее обновление этой страницы: 2025-07-12 15:11:36Z