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

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

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

I’m not crazy. My mother had me tested. © Sheldon

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.
👍ПодобаєтьсяСподобалось2
До обраногоВ обраному1
LinkedIn
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

От питання власне стосовно Ерланга: для чого в сучасному світі використовуються актори (заради них же мову робили, ніби) і якого вони розміру в реальних проектах. Якісь приклади data flow / control flow систем, і чому взяли ерланг, а не С++ або Go або Akka.

Дякуємо за питання, хоча воно не відноситься до цієї статті :-). Erlang використовують для величезної кількості проєктів різних напрямків наприклад: blockchain(github.com/aeternity), messengers(github.com/WhatsApp, github.com/processone/ejabberd), mobile core networking(github.com/travelping/ergw, github.com/travelping/eradius), banking(github.com/rabbitmq, github.com/otp-bank), gaming(github.com/wgnet), machine learning(www.modelop.com), web scraping(github.com/scrapinghub) и багато інших проєктів де використовують Erlang. Чому саме для Sheldon був вибраний Erlang для перевірки орфографії? — тому що вже є багато подібних проєктів на інших мовах серед яких C, C++, Python etc., але саме на Erlang не має. Також існує багато проєктів на Erlang яким може бути корисний Sheldon. Звісно, є можливість інтигрувати C проєкт в Erlang завдяки erlang.org/...​4/doc/tutorial/cnode.html та www.erlang.org/doc/tutorial/c_port.html але це трохи інший напрямок та ідея.

Ну от я намагався зрозуміти, які є практичні архітектурні переваги Erlang, але замість відповіді було наведено список проектів.

Розумієте все залежить від певних вимог та потреб, але якщо корото за рахунок анкорної моделі та відмовостійкої системи яка працює в режимі м’якого реального часу загалом надають перевагу саме Erlang як для веб сервісів с монолітною архитектурую для месенджерів так і для мікросервісів для платіжних систем в банках. Перелік проєктів я надав через те щоб показати які продукти використовують Erlang сьогодні. Так як все в open source, можливо буде цікаво порівняти їх.

Якби то були архітектурні діаграми — можна було б щось порівняти. А наскільки абсурдною виглядає ідея порівняння сервісів за їх відкритим кодом — думаю, ви розумієте.

Розумію про що Ви, але як я вже писав раніше, я буду намагатися створити статтю для більш детального опису де намагатимуся надати діаграми та результати бенчмарків. Також я прошу звернути Вашу увагу на те що проекти в open source намагаються надаты багато інформації — на приклад статтi, бенчмарки та workshops наприклад про те як один вузол з 2+ мільйонами одночасних користувачів працює без збоїв та проблем, але для того чтоб порівняти ті чи інші проекти потрібно визначитися з областю, напрямком та проблемами. Erlang це не панацея від усіх хвороб та не завжди Erlang це корисний вибiр для продукту. Хоча в той же час якщо ми говоримо про сервіси, я не один раз зустрічав клієнтів, які вирішили переписати з Java на Erlang свої продукти і бачив як два розробники на Erlang переписували продукти які розроблялися роками всього за три місяці при цьому вони добивались вражаючих результатів щодо витримування досить великих навантажень. Якщо у Вас буде час я рекомендую подивитися це відео(www.youtube.com/watch?v=JvBT4XBdoUE) про переваги Erlang, його віртуальну машину, а також про те, коли і чому варто розглянути можливість його використання.

Мене цікавить не власне Ерланг, а порівняння підтримки акторів у різних мовах, і які саме типи систем на акторах пишуть. Також для оглядової статті стосовно архітектур на акторах.

Дякую за відео. Схоже на Акка.

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

Підписатись на коментарі