1. Обзор

spellfix1 это виртуальная таблица, которая может использоваться, чтобы искать близкие соответствия в большом словаре. Например, spellfix1 может использоваться, чтобы предложить исправления словам с орфографической ошибкой. Или, это могло использоваться с FTS4, чтобы сделать полнотекстовый поиск, потенциально использующий слова c орфографическими ошибками.

Внедрение для 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='*';

Можно также предоставить виртуальной таблице "rank" для каждого слова. "rank" это оценка того, насколько распространено слово. Большее число означает, что слово более распространено. Если вы опускаете разряд, наполняя таблицу, то разряд 1 принят. Но если у вас есть информация о разряде, можно поставлять ее, и виртуальная таблица покажет небольшое предпочтение отбора чаще всего используемых терминов. Чтобы наполнить rank из таблицы 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 для единственного языкового id. Нет никакого способа искать все языки сразу.

3. Виртуальные детали таблицы

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

rowid

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

word

Текст слова, которое соответствует образцу. Слово и образец могут содержать знаки unicode и могут быть смешанным регистром.

rank

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

distance

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

langid

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

score

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

matchlen

В поиске префикса matchlen это количество знаков в последовательности, которые соответствуют префиксу. Для поиска непрефикса это совпадает с length(word).

phonehash

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

top

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

scope

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

srchcnt

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

soundslike

(Скрытый) Вставляя записи словаря, эта область может быть установлена в правописание, которое соответствует тому, на что походит слово.

command

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

4. Алгоритм

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

id

Уникальный id (INTEGER PRIMARY KEY)

rank

rank слова.

langid

language id записи.

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, Метателефоне и других давних фонетических системах соответствия. Этот ключ может быть произведен функцией spellfix1_phonehash(X). Следовательно: k2 = spellfix1_phonehash(coalesce(k1,word))

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

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

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

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

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

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

Например, предположите, что входное слово "Paskagula". Фонетический ключ "BACACALA", который усечен к 4 знакам "BACA". Расстоянием тогда управляют на этих 4980 записях (из 272597 суммарно) словаря, значения k2 которого начинаются с BACA, приводя к "Pascagoula" как к лучшему совпадению.

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

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

Встроенная функция Wagner edit-distance с фиксированными весами может быть заменена функцией editdist3() с определенными применением весами и поддержкой unicode, определив "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" виртуальной таблицы заставляет коэффициенты расстояния быть перечитанными. Следовательно, запросы должны управлять 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');

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

Упомянутый ниже некоторые случаи, где могло бы иметь смысл добавлять дополнительные подобные звуку записи. Определенные записи будут зависеть от применения и выходного языка.

• Непроизносимое "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)

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

spellfix1_scriptcode(X)

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

• 215 - Latin
• 220 - Cyrillic
• 200 - Greek

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

spellfix1_translit(X)

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

8. Функция editdist3

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

• Это работает с текстом в unicode (UTF8).

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

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

9. Таблица editdist3 COST

Чтобы программировать затраты на 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()". Она имеет 3 формы:

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

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

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