Sheldon: Erlang-бібліотека для перевірки орфографії

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті.

Всім привіти! Мене звати В’ячеслав Кацуба, і я надаю консалтингові послуги з Erlang протягом останніх 6 років для проєктів з різними напрямками. У цій статті я хочу поговорити про один цікавий проєкт з відкритим кодом Sheldon, написаний на Erlang.

Sheldon — це проста бібліотека для перевірки орфографії за допомогою Erlang, яка пропонує правильні слова, коли певне слово написане з помилкою. Цю бібліотеку створив Феліпе Ріполл для Inaka.

Вперше про Шелдона я почув від Брухо (Фернандо) Бенавідеса, коли ми обговорювали ідеї створення плагінів для rebar3. Після деяких досліджень проєкту я був вражений ідеєю. Тим не менш, перед написанням плагіна для цього чудового проєкту потрібно було виправити декілька цікавих проблем. Тому я почав глибше копатися в Шелдоні, щоб спробувати покращити його.

Що таке Шелдон?

Спершу дозвольте мені показати вам, що вміє Шелдон.

1> sheldon:start().
ok
2> sheldon:check("I want to check this correct text").
ok
3> sheldon:check("I want to check this misspeled text").
#{bazinga => <<"That's no reason to cry. One cries because one is sad. For example, I cry because others are stupid, and that ma"...>>,
 misspelled_words => [#{candidates => ["misspeed","misspelled"],
    line_number => 1,
    word => "misspeled"}]}

Отже, як він працює? У своїх перших версіях Шелдон використовував алгоритм Пітера Норвіга.

Коротко, цей алгоритм використовує наступний підхід — на вхід ми отримуємо слово, спочатку перевіряємо наявність цього слова у заздалегідь підготовленому словнику. Потім, якщо ми не знайшли слова у словнику, ми розуміємо, що це кандидат на виправлення орфографії та намагаємося застосувати посимвольне видалення, вставку та делегування символів всередині самого слова. Потім такий самий підхід застосовується з додаванням додаткового символу, взятого з алфавіту. Звичайно, кожне слово перевіряється у словнику і коли знаходить гадані варіанти — він їх репрезентує у відповідь.

Цей алгоритм працює досить добре. Однак пізніше я виявив, що у нього була одна велика проблема: для досить великих слів (наприклад, в англійській мові це — «Pneumonoultramicroscopicsilicovolcanoconiosis» що становить довжину в 45 символів), алгоритм генерує занадто багато можливих альтернатив, а саме — 11553868 можливих варіантів зі слова, яке містить 45 символів.

Час обробки цього алгоритму тільки для одного схожого слова може тривати в середньому близько 9 секунд. Звісно, щоразу проводити таку перевірку досить дорого як по часу, так і для RAM з CPU. Тому я вирішив оптимізувати цей алгоритм, і після деяких змін коду вдалося досягти швидкості приблизно в одну секунду для великих слів.

Для довідки — інші алгоритми та проєкти можуть обробляти 2 тисячі слів приблизно за дві секунди, тобто якщо ми запустимо ті самі бенчмарки в Шелдоні, тільки сформуємо 2 тисячі неправильних слів, що складаються з 45 символів кожне, нам доведеться чекати на результат тестів 2000 секунд замість двох очікуваних секунд.

Звичайно, з такою швидкістю інтегрувати Шелдона в якийсь інший проєкт було не дуже гарною ідеєю. Тому я вирішив спробувати знайти інший шлях. Погугливши, я знайшов ці цікаві статті:

SymSpell vs. BK-tree: 100x faster fuzzy string search & spell checking англійською мовою та Исправляем опечатки с учетом контекста російською мовою. У цих статтях автори подають багато корисної інформації.

В обох статтях йдеться про алгоритм SymSpell. Алгоритм SymSpell, по суті, є сукупністю певного набору різних алгоритмів, але те, що привернуло мою увагу, це саме модель індексованих помилок. Ідея моделі помилок досить проста: створюється логіка для генерування помилки, яка видаляє кожен символ через один або два символи та повʼязує згенероване слово з правильним словом з словника.

Скажімо, у нас є правильне слово тест. У цьому разі індексами цього слова будуть: екст, тст, тет, тес. Тепер давайте спробуємо перевірити неправильне слово темт. Індексами цього слова будуть емт, тмт, тет, емт. Якщо ми порівняємо ці два списки індексів, то побачимо, що тет належить до обох. Оскільки ми знаємо, що текст є правильним словом, яке є у словнику, це означає, що воно має бути одним із наших кандидатів.

Підвищення продуктивності Шелдона за допомогою SymSpell-like

Моїм першим кроком до покращення Шелдона була заміна алгоритму Пітера Норвіга на SymSpell-like алгоритм. Давайте перевіримо його вплив на продуктивність після змін.

%% Peter Norvig для одного неправильного великого слова без модифікації
1> LongWord = base64:encode(crypto:strong_rand_bytes(45)).
2> timer:tc(sheldon, check, [LongWord]).
{8693825, %% Більше ніж 8.5 скунди
#{bazinga => <<"I know the real reason you "...>>,
  misspelled_words => [
     #{candidates => [],
       line_number => 1,
       word =>"AA9VaG90nSWUwdEQYs+lqTBZRU1vBaxjK7iU/1..."}]}}

%% SymSpell-like алгоритм для перевірки 2 тисячь неправильних слів
1> LongWord = base64:encode(crypto:strong_rand_bytes(45)).
2> timer:tc(fun() ->
    [begin
      {T, _} = timer:tc(sheldon, check, [LongWord]),
      T
    end || _ <- lists:seq(1, 2000)] end). 
{1109351, %% Approximately 1.1 seconds
[2955,2360,2285,2378,2998,2711,2743,2411,2547,2756,2681,
 2373,1683,2393,2229,1551,1532,1149,799,1541,1326,1130,877,
 1142,834,737,802|...]}

SymSpell-like алгоритм показав швидкість обробки в 1,109351 секунди для двох тисяч неправильних слів довжиною 45 символів кожне. Дійсно дуже швидко, особливо порівняно з оригінальним алгоритмом, використаним у Шелдоні до перших модіфікацій.

Більше покращень

Тепер, коли ми досягли такої вражаючої швидкості, Шелдон був готовий до інтеграції в будь-який проект. Але все-таки Шелдону потрібно було ще кілька модифікацій, пов’язаних із конфігурацією, щоб бути дійсно корисним та гнучким у використанні. У серію запитів на витяг (pull requests) я додав декілька новинок в основний функціонал, який ви можете побачити нижче:

%% Слово "Sheldon" не існує в словнику за замовчуванням
1> sheldon:check("Sheldon doesn't know his name").
#{bazinga => <<"I am not crazy, my mother had me tested.">>,
 misspelled_words =>
     [#{candidates => ["Sheldon"],
        line_number => 1,word => "Sheldon"}]
2> Config = #{ignore_words => ["Sheldon"]}.    %% Ігнорувати слово у тексті 
3> ok = sheldon:check("Sheldon doesn't know his name", Config).
4> Config2 = #{ignore_patterns => ["^begin"]}. %% Ігнорувати по регулярному виразу
5> ok = sheldon:check("begindddd should be ignored", Config).

За замовчуванням Sheldon є засобом перевірки правопису звичайного тексту (тобто він нічого не знає про форматування тексту у вигляді HTML або Markdown), але однією з його чудових функцій є можливість розширити аналіз тексту за допомогою адаптерів. Я не додавав цю функцію, але я думаю, що це дуже круто, і про це варто згадати в цій статті. Ці адаптери потрібні, наприклад, коли вам потрібно перевірити орфографію HTML або текст в Markdown. Адаптер Markdown вже реалізований і може використовуватися таким чином:

%% Ігнорувати блоки та використовувати адаптер markdown
1> Config =
#{adapters => [markdown_adapter],
 ignore_blocks =>
     [#{close => "^end-block$",open => "^start-block$"},
      #{close => "^end-block1$",open => "^start-block1$"}]}.
2> MarkdownText = "start-block\nsome text\nend-block$".
3> ok = sheldon:check(MarkdownText, Config).

Якщо поточний адаптер з якоїсь причини не підходить вам — ви можете створити та застосувати свою поведінку (behavior). Щоб створити власний адаптер для користувацького маніпулювання текстом, вам потрібно реалізувати поведінку sheldon_adapter:

-module(own_adapter).

-behaviour(sheldon_adapter).

-export([adapt/1]).

-spec adapt(binary()) -> iodata().
adapt(Line) ->
   custom_manipulation:text(Line).

За замовчуванням Шелдон використовує власний словник англійської мови. Звичайно, не всі види слів додаються до цього словника, і іноді потрібно доповнити словник власним набором слів. З цієї причини я вирішив додати нову опцію конфігурації, яка буде використовуватися, коли вам потрібно розширити словник за замовчуванням. Тепер ви можете використовувати цю конфігурацію у своєму додатку:

[{sheldon, [
   {additional_dictionary,
     ["path/to/additional_dictionary.txt",                     
      "path/to/other_additional_dictionary.txt"]}]}].

У попередніх версіях також неможливо було замінити словник за замовчуванням на користувацький. Я створив нову опцію конфігурації, щоб встановити спеціальний словник за замовчуванням. Тепер ви можете повністю замінити словник за замовчуванням, використовуючи наступну конфігурацію:

[{sheldon, [
   {default_dictionary, "path/to/your/default_dictionary.txt"}]}].

Також звичайно, ви можете комбінувати обидві опції:

[{sheldon, [
 {default_dictionary, "path/to/your/default_dictionary.txt"},
 {additional_dictionary,
   ["path/to/additional_dictionary.txt",                     
    "path/to/other_additional_dictionary.txt"]}]}].

Майбутній розвиток

Звісно нинішня реалізація Шелдона все-одно вимагає більше любові, та, звичайно, Шелдон її отримає.

Серед майбутніх удосконалень варто відзначити, що Шелдон зосереджений лише на англійській мові, але в майбутньому ми хочемо додати підтримку словників Unicode, де користувач зможе встановлювати різні словники для рiзних мов.

Крім того, разом з Brujo ми створили плагін rebar3_sheldon для перевірки орфографії тексту в рядках, двійкових даних і коментарях у вихідному коді Erlang-проєктів, побудованих на rebar3, але ми поговоримо про цей плагін та його можливості у наступній статті.

Крім того, у Феліпе Ріполла, у Брухо (Фернандо) Бенавідеса, в мене та інших є багато ідей щодо того, як розширити, покращити або використовувати Шелдон. Але нам знадобиться допомога для їх реалізації. Отже, якщо ви хочете приєднатися до нас у цій роботі, ви можете знайти нас у #sheldon кімнаті Erlang Slack. Дайте нам пінг там, і ви зможете стати частиною цього фантастичного проекту.

Посилання:

• Ви також можете знайти Шелдона на hex.pm.
• Або ви можете зробити свій внесок у проєкт безпосередньо на GitHub.