Исправление орфографии, также известное как:

• Автоматическая коррекция
• Коррекция текста
• Исправление орфографических ошибок
• Толерантность к опечаткам
• "Вы имели в виду?"

и так далее, — это программная функция, которая предлагает альтернативы или автоматически исправляет введённый вами текст. Концепция исправления набранного текста восходит к 1960-м годам, когда учёный-компьютерщик Уоррен Тейтельман, также изобретший команду "отменить", представил философию вычислений под названием D.W.I.M., или "Do What I Mean" (делай, что я имею в виду). Вместо того чтобы программировать компьютеры принимать только идеально отформатированные инструкции, Тейтельман утверждал, что их следует программировать на распознавание очевидных ошибок.

Первым известным продуктом, предоставляющим функцию исправления орфографии, был Microsoft Word 6.0, выпущенный в 1993 году.

Существует несколько способов реализации исправления орфографии, но важно отметить, что не существует чисто программного способа с достойным качеством преобразовать вашу ошибочно набранную "ipone" в "iphone". В основном, должна быть база данных, на которой основана система. Эта база данных может быть:

• Словарём правильно написанных слов, который, в свою очередь, может быть:
  • Основан на ваших реальных данных. Идея здесь в том, что, в основном, орфография в словаре, составленном из ваших данных, правильная, и система пытается найти слово, наиболее похожее на введённое (мы вскоре обсудим, как это можно сделать с помощью Manticore).
  • Или он может основываться на внешнем словаре, не связанном с вашими данными. Проблема, которая может возникнуть здесь, заключается в том, что ваши данные и внешний словарь могут слишком сильно отличаться: некоторые слова могут отсутствовать в словаре, в то время как другие могут отсутствовать в ваших данных.
• Не только основанным на словаре, но и учитывающим контекст, например, "white ber" будет исправлено на "white bear", а "dark ber" — на "dark beer". Контекстом может быть не только соседнее слово в вашем запросе, но и ваше местоположение, время суток, грамматика текущего предложения (чтобы изменить "there" на "their" или нет), история ваших поисков и практически любые другие факторы, которые могут повлиять на ваш замысел.
• Ещё один классический подход — использовать предыдущие поисковые запросы в качестве базы данных для исправления орфографии. Это ещё больше используется в функционале автозаполнения, но также имеет смысл и для автокоррекции. Идея в том, что пользователи в основном правильно пишут слова, поэтому мы можем использовать слова из их истории поиска как источник истины, даже если у нас нет этих слов в наших документах или мы не используем внешний словарь. Здесь также возможна учёт контекста.

Manticore предоставляет опцию нечеткого поиска и команды CALL QSUGGEST и CALL SUGGEST, которые можно использовать для автоматического исправления орфографии.

Функция нечеткого поиска позволяет более гибко сопоставлять, учитывая небольшие вариации или опечатки в поисковом запросе. Она работает аналогично обычному SQL-запросу SELECT или JSON-запросу /search, но предоставляет дополнительные параметры для управления поведением нечеткого сопоставления.

ПРИМЕЧАНИЕ: Опция fuzzy требует Manticore Buddy. Если она не работает, убедитесь, что Buddy установлен.

ПРИМЕЧАНИЕ: Опция fuzzy недоступна для мультизапросов.

SELECT
  ...
  MATCH('...')
  ...
  OPTION fuzzy={0|1}
  [, distance=N]
  [, preserve={0|1}]
  [, layouts='{be,bg,br,ch,de,dk,es,fr,uk,gr,it,no,pt,ru,se,ua,us}']
}

SELECT * FROM mytable WHERE MATCH('someting') OPTION fuzzy=1, layouts='us,ua', distance=2;

SELECT * FROM mytable WHERE MATCH('someting') OPTION fuzzy=1 AND (category='books' AND price < 20);

POST /search
{
  "table": "test",
  "query": {
    "bool": {
      "must": [
        {
          "match": {
            "*": "ghbdtn"
          }
        }
      ]
    }
  },
  "options": {
    "fuzzy": true,
    "layouts": ["us", "ru"],
    "distance": 2
  }
}

SELECT * FROM mytable WHERE MATCH('hello wrld') OPTION fuzzy=1, preserve=1;

POST /search
{
  "table": "test",
  "query": {
    "bool": {
      "must": [
        {
          "match": {
            "*": "hello wrld"
          }
        }
      ]
    }
  },
  "options": {
    "fuzzy": true,
    "preserve": 1
  }
}

+------+-------------+
| id   | content     |
+------+-------------+
|    1 | something   |
|    2 | some thing  |
+------+-------------+
2 rows in set (0.00 sec)

+------+-------------+
| id   | content     |
+------+-------------+
|    1 | hello wrld  |
|    2 | hello world |
+------+-------------+
2 rows in set (0.00 sec)

POST /search
{
  "table": "table_name",
  "query": {
    <full-text query>
  },
  "options": {
    "fuzzy": {true|false}
    [,"layouts": ["be","bg","br","ch","de","dk","es","fr","uk","gr","it","no","pt","ru","se","ua","us"]]
    [,"distance": N]
    [,"preserve": {0|1}]
  }
}

Примечание: Если вы используете query_string, имейте в виду, что он не поддерживает полнотекстовые операторы, кроме оператора поиска фразы. Строка запроса должна состоять только из слов, которые вы хотите сопоставить.

• fuzzy: Включить или выключить нечеткий поиск.
• distance: Установить расстояние Левенштейна для сопоставления. По умолчанию 2.
• preserve: 0 или 1 (по умолчанию: 0). При установке в 1 сохраняет слова, для которых не найдено нечетких совпадений в результатах поиска (например, "hello wrld" возвращает и "hello wrld", и "hello world"). При установке в 0 возвращает только слова с успешными нечеткими совпадениями (например, "hello wrld" возвращает только "hello world"). Особенно полезно для сохранения коротких слов или собственных имён, которые могут отсутствовать в Manticore Search.
• layouts: Раскладки клавиатуры для обнаружения ошибок набора, вызванных несоответствием раскладки клавиатуры (например, набор "ghbdtn" вместо "привет" при неправильной раскладке). Manticore сравнивает позиции символов в разных раскладках для предложения исправлений. Требуется минимум 2 раскладки для эффективного обнаружения несоответствий. По умолчанию раскладки не используются. Используйте пустую строку '' (SQL) или массив [] (JSON), чтобы отключить эту функцию. Поддерживаемые раскладки включают:
  • be - бельгийская раскладка AZERTY
  • bg - стандартная болгарская раскладка
  • br - бразильская раскладка QWERTY
  • ch - швейцарская раскладка QWERTZ
  • de - немецкая раскладка QWERTZ
  • dk - датская раскладка QWERTY
  • es - испанская раскладка QWERTY
  • fr - французская раскладка AZERTY
  • uk - британская раскладка QWERTY
  • gr - греческая раскладка QWERTY
  • it - итальянская раскладка QWERTY
  • no - норвежская раскладка QWERTY
  • pt - португальская раскладка QWERTY
  • ru - русская раскладка JCUKEN
  • se - шведская раскладка QWERTY
  • ua - украинская раскладка JCUKEN
  • us - американская раскладка QWERTY

• Эта демонстрация показывает функциональность нечеткого поиска:
• Пост в блоге о нечетком поиске и автозаполнении - https://manticoresearch.com/blog/new-fuzzy-search-and-autocomplete/

Обе команды доступны через SQL и поддерживают запросы как к локальным (обычным и реального времени), так и к распределённым таблицам. Синтаксис следующий:

CALL QSUGGEST(<word or words>, <table name> [,options])
CALL SUGGEST(<word or words>, <table name> [,options])
options: N as option_name[, M as another_option, ...]

Эти команды предоставляют все предложения из словаря для заданного слова. Они работают только с таблицами, у которых включён infixing и dict=keywords. Они возвращают предложенные ключевые слова, расстояние Левенштейна между предложенным и исходным ключевым словом, а также статистику документов по предложенному ключевому слову.

Если первый параметр содержит несколько слов, то:

• CALL QSUGGEST вернёт предложения только для последнего слова, игнорируя остальные.
• CALL SUGGEST вернёт предложения только для первого слова.

Это единственное различие между ними. Поддерживается несколько опций для настройки:

Чтобы показать, как это работает, создадим таблицу и добавим в неё несколько документов.

create table products(title text) min_infix_len='2';
insert into products values (0,'Crossbody Bag with Tassel'), (0,'microfiber sheet set'), (0,'Pet Hair Remover Glove');

call suggest('crossbudy', 'products');

+-----------+----------+------+
| suggest   | distance | docs |
+-----------+----------+------+
| crossbody | 1        | 1    |
+-----------+----------+------+

call suggest('bagg with tasel', 'products');

+---------+----------+------+
| suggest | distance | docs |
+---------+----------+------+
| bag     | 1        | 1    |
+---------+----------+------+

CALL QSUGGEST('bagg with tasel', 'products');

+---------+----------+------+
| suggest | distance | docs |
+---------+----------+------+
| tassel  | 1        | 1    |
+---------+----------+------+

CALL QSUGGEST('bag with tasel', 'products', 1 as sentence);

+-------------------+----------+------+
| suggest           | distance | docs |
+-------------------+----------+------+
| bag with tassel   | 1        | 1    |
+-------------------+----------+------+

Опция 1 as result_line меняет способ отображения предложений в выводе. Вместо того, чтобы показывать каждое предложение в отдельной строке, она выводит все предложения, расстояния и документы в одной строке. Вот пример для демонстрации:

CALL QSUGGEST('bagg with tasel', 'products', 1 as result_line);

+----------+--------+
| name     | value  |
+----------+--------+
| suggests | tassel |
| distance | 1      |
| docs     | 1      |
+----------+--------+

Опция force_bigrams помогает с словами, в которых есть ошибки перестановки, например "ipohne" вместо "iphone". Используя биграммы вместо триграмм, алгоритм лучше справляется с перестановками символов.

CALL SUGGEST('ipohne', 'products', 1 as force_bigrams);

+--------+----------+------+
| suggest| distance | docs |
+--------+----------+------+
| iphone | 2        | 1    |
+--------+----------+------+

• Этот интерактивный курс показывает, как работает CALL SUGGEST в небольшом веб-приложении.

Кэш запросов хранит сжатые наборы результатов в памяти и повторно использует их для последующих запросов, когда это возможно. Вы можете настроить его с помощью следующих директив:

• qcache_max_bytes — ограничение на использование ОЗУ для хранения кэшированных запросов. По умолчанию 16 МБ. Установка qcache_max_bytes в 0 полностью отключает кэш запросов.
• qcache_thresh_msec — минимальное время выполнения запроса (в миллисекундах) для кэширования. Запросы, которые выполняются быстрее этого времени, не будут кэшироваться. По умолчанию 3000 мс, или 3 секунды.
• qcache_ttl_sec — время жизни кэшированной записи. Запросы будут храниться в кэше в течение этого времени. По умолчанию 60 секунд, или 1 минута.

Эти настройки можно изменять на лету с помощью оператора SET GLOBAL:

mysql> SET GLOBAL qcache_max_bytes=128000000;

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

Кэш запросов работает следующим образом. Когда он включен, каждый результат полнотекстового поиска полностью сохраняется в памяти. Это происходит после полнотекстового сопоставления, фильтрации и ранжирования, то есть по сути мы сохраняем пары {docid,weight} для total_found. Сжатые совпадения могут занимать в среднем от 2 до 12 байт на совпадение, в основном в зависимости от дельт между последовательными docid. После завершения запроса мы проверяем пороги времени выполнения и размера, и либо сохраняем сжатый набор результатов для повторного использования, либо отбрасываем его.

Обратите внимание, что влияние кэша запросов на ОЗУ не ограничивается qcache_max_bytes! Если, например, выполняется 10 параллельных запросов, каждый из которых совпадает с до 1 млн совпадений (после фильтров), то пиковое временное использование ОЗУ будет в диапазоне от 40 МБ до 240 МБ, даже если запросы достаточно быстрые и не кэшируются.

Запросы могут использовать кэш, когда совпадают таблица, полнотекстовый запрос (то есть содержимое MATCH()) и ранжировщик, а фильтры совместимы. Это означает:

• Полнотекстовая часть внутри MATCH() должна совпадать посимвольно. Добавьте один дополнительный пробел — и для кэша запросов это уже другой запрос.
• Ранжировщик (и его параметры, если есть, для пользовательских ранжировщиков) должен совпадать посимвольно.
• Фильтры должны быть надмножеством исходных фильтров. Вы можете добавить дополнительные фильтры и всё равно попасть в кэш. (В этом случае дополнительные фильтры будут применены к кэшированному результату.) Но если вы уберёте какой-то фильтр, это будет уже новый запрос.

Записи кэша истекают по TTL и также инвалидируются при ротации таблицы, или при выполнении TRUNCATE, или ATTACH. Обратите внимание, что в настоящее время записи не инвалидируются при произвольных записях в RT-таблицы! Поэтому кэшированный запрос может возвращать устаревшие результаты в течение времени жизни TTL.

Вы можете просмотреть текущий статус кэша с помощью SHOW STATUS через переменные qcache_XXX:

mysql> SHOW STATUS LIKE 'qcache%';
+-----------------------+----------+
| Counter               | Value    |
+-----------------------+----------+
| qcache_max_bytes      | 16777216 |
| qcache_thresh_msec    | 3000     |
| qcache_ttl_sec        | 60       |
| qcache_cached_queries | 0        |
| qcache_used_bytes     | 0        |
| qcache_hits           | 0        |
+-----------------------+----------+
6 rows in set (0.00 sec)

Сопоставления в первую очередь влияют на сравнения строковых атрибутов. Они определяют как кодировку набора символов, так и стратегию, которую Manticore использует для сравнения строк при выполнении ORDER BY или GROUP BY с участием строкового атрибута.

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

Во-первых, строки с однобайтовой кодировкой (ASCII, ISO-8859-1 или Windows-1251) нужно обрабатывать иначе, чем строки в UTF-8, которые могут кодировать каждый символ переменным числом байт. Следовательно, нам нужно знать тип набора символов, чтобы правильно интерпретировать сырые байты как значимые символы.

Во-вторых, нам также нужны правила сортировки, специфичные для языка. Например, при сортировке по правилам США в локали en_US, акцентированный символ ï (маленькая буква i с умлаутом) должен располагаться где-то после z. Однако при сортировке по французским правилам и локали fr_FR он должен располагаться между i и j. Другой набор правил может вообще игнорировать акценты, позволяя произвольно смешивать ï и i.

В-третьих, в некоторых случаях требуется сортировка с учётом регистра, а в других — без учёта регистра.

Сопоставления инкапсулируют всё следующее: набор символов, языковые правила и чувствительность к регистру. В настоящее время Manticore предоставляет четыре сопоставления:

1. libc_ci
2. libc_cs
3. utf8_general_ci
4. binary

Первые два сопоставления опираются на несколько стандартных вызовов библиотеки C (libc) и, следовательно, могут поддерживать любую локаль, установленную в вашей системе. Они обеспечивают сравнения без учёта регистра (_ci) и с учётом регистра (_cs) соответственно. По умолчанию они используют локаль C, фактически сводя сравнения к побайтовым. Чтобы изменить это, нужно указать другую доступную локаль с помощью директивы collation_libc_locale. Список локалей, доступных в вашей системе, обычно можно получить с помощью команды locale:

$ locale -a
C
en_AG
en_AU.utf8
en_BW.utf8
en_CA.utf8
en_DK.utf8
en_GB.utf8
en_HK.utf8
en_IE.utf8
en_IN
en_NG
en_NZ.utf8
en_PH.utf8
en_SG.utf8
en_US.utf8
en_ZA.utf8
en_ZW.utf8
es_ES
fr_FR
POSIX
ru_RU.utf8
ru_UA.utf8

Конкретный список локалей системы может отличаться. Обратитесь к документации вашей ОС для установки дополнительных необходимых локалей.

Локали utf8_general_ci и binary встроены в Manticore. Первая — это универсальное сопоставление для данных UTF-8 (без так называемой языковой адаптации); оно должно вести себя аналогично сопоставлению utf8_general_ci в MySQL. Вторая — простое побайтовое сравнение.

Сопоставление можно переопределить через SQL на уровне сессии с помощью оператора SET collation_connection. Все последующие SQL-запросы будут использовать это сопоставление. В противном случае все запросы будут использовать сопоставление по умолчанию сервера или указанное в директиве конфигурации collation_server. В настоящее время Manticore по умолчанию использует сопоставление libc_ci.

Сопоставления влияют на все сравнения строковых атрибутов, включая те, что внутри ORDER BY и GROUP BY, поэтому в зависимости от выбранного сопоставления могут возвращаться результаты с разным порядком или группировкой. Обратите внимание, что сопоставления не влияют на полнотекстовый поиск; для этого используйте charset_table.

Когда Manticore выполняет запрос полного сканирования, он может либо использовать простой скан для проверки каждого документа по фильтрам, либо применять дополнительные данные и/или алгоритмы для ускорения выполнения запроса. Manticore использует оптимизатор на основе стоимости (CBO), также известный как «оптимизатор запросов», чтобы определить, какой подход выбрать.

CBO также может улучшить производительность полнотекстовых запросов. Подробнее см. ниже.

CBO может решить заменить один или несколько фильтров запроса одним из следующих элементов, если он определит, что это улучшит производительность:

1. docid индекс использует специальный вторичный индекс только по docid, хранящийся в файлах с расширением .spt. Помимо улучшения фильтров по идентификаторам документов, docid индекс также используется для ускорения поиска соответствия docid к rowid и для ускорения применения больших списков исключений (killlists) при запуске демона.
2. Колоннарное сканирование опирается на колоннарное хранение и может использоваться только для колоннарного атрибута. Оно сканирует каждое значение и проверяет его по фильтру, но при этом сильно оптимизировано и обычно быстрее стандартного подхода.
3. Вторичные индексы создаются по умолчанию для всех атрибутов (кроме JSON). Они используют PGM индекс вместе с встроенным инвертированным индексом Manticore для получения списка rowid, соответствующих значению или диапазону значений. Вторичные индексы хранятся в файлах с расширениями .spidx и .spjidx. Для информации о том, как создавать вторичные индексы по JSON-атрибутам, см. json_secondary_indexes.

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

1. Информацию о распределении данных внутри атрибута (гистограммы, хранящиеся в файлах .sphi). Гистограммы генерируются автоматически при индексировании данных и служат основным источником информации для CBO.
2. Информацию из PGM (вторичные индексы), которая помогает оценить количество списков документов для чтения. Это помогает оценить производительность слияния doclist и выбрать подходящий алгоритм слияния (слияние с приоритетной очередью или слияние битмапов).
3. Статистику колоннарного кодирования, используемую для оценки производительности декомпрессии колоннарных данных.
4. Колоннарное дерево min-max. В то время как CBO использует гистограммы для оценки количества документов, оставшихся после применения фильтра, ему также нужно определить, сколько документов фильтр должен был обработать. Для колоннарных атрибутов частичная оценка дерева min-max служит этой цели.
5. Полнотекстовый словарь. CBO использует статистику терминов для оценки стоимости вычисления полнотекстового дерева.

Оптимизатор вычисляет стоимость выполнения для каждого фильтра, используемого в запросе. Поскольку некоторые фильтры могут быть заменены несколькими разными элементами (например, для идентификатора документа Manticore может использовать простой скан, поиск по docid индексу, колоннарное сканирование (если docid колоннарный) и вторичный индекс), оптимизатор оценивает все доступные комбинации. Однако существует максимальный предел в 1024 комбинации.

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

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

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

Еще одним фактором является многопоточное выполнение запроса (когда включен pseudo_sharding). CBO учитывает, что некоторые запросы могут выполняться в нескольких потоках, и принимает это во внимание. CBO отдает приоритет более короткому времени выполнения запроса (то есть задержке), а не пропускной способности. Например, если запрос с использованием колоннарного сканирования может выполняться в нескольких потоках (и занимать несколько ядер CPU) и при этом быстрее, чем запрос, выполняемый в одном потоке с использованием вторичных индексов, будет предпочтено многопоточное выполнение.

Запросы с использованием вторичных индексов и docid индексов всегда выполняются в одном потоке, так как бенчмарки показывают, что многопоточное выполнение для них малоэффективно.

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