Коли регулярки дають право на помилку: занурення у нечіткий пошук з TreRegex для Ruby та Node.js

Усі ми знаємо класичний бородатий жарт Джеймі Завінські: «Деякі люди, коли стикаються з проблемою, думають: „О, я використаю регулярні вирази“. Тепер у них дві проблеми».

Але що робити, якщо ваша проблема — це текст, який пройшов крізь пекло OCR-розпізнавання (Optical Character Recognition), де половина літер перетворилася на цифрове сміття, або користувачі, які пишуть пошукові запити так, наче купували клавіатуру наосліп? Якщо ви спробуєте нацькувати на такий текст стандартний Regexp, ви отримаєте рівно нуль збігів. А якщо ви виберете шлях написання регулярки, яка покриває всі можливі помилки, то у вас з’явиться не дві проблеми, а повноцінний квиток у вигорання.

Звісно, можна згадати про відстань Левенштейна. Але класичні алгоритми обчислення відстаней зазвичай порівнюють рядок зі рядком цілком. А якщо нам потрібно знайти криве слово всередині гігантського масиву тексту?

Для цього я зібрав і випустив TreRegex — інструмент для швидкого, асиметричного та наближеного (fuzzy) пошуку за регулярними виразами для Ruby та Node.js. Тепер ви можете дозволити своїм регуляркам помилятися — строго контрольовано і з мінімальним перформанс-оверхедом.

OCR, перевірки та біль розробника

Уявіть реальну бізнес-задачу: ви парсите скановані чеки або документи. На папері було написано слово algorithm. Але сканер разом із OCR-лібою вирішили відсвяткувати п’ятницю, і на виході ви отримали algoritm (пропущена літера) або algorethm (заміна літери).

Стандартний двигун регулярних виразів у вашій мові програмування (на кшталт PCRE чи Onigmo) — це перфекціоніст. Він шукає ідеальний збіг. Нечіткий пошук у TreRegex працює інакше: він дозволяє задати патерн і вказати максимальну «ціну помилки» або кількість помилок (вставок, видалень чи замін), які алгоритм може пробачити тексту.

В основі бібліотеки лежить TRE рушій від Лаурі Карі. Він реалізує алгоритми approximate matching, розширюючи стандартні регулярні вирази POSIX. Замість того, щоб будувати гігантські NFA-автомати в JS чи Ruby, ми віддаємо цю брудну роботу низькорівневому С-коду, який виконує це максимально швидко.

Два світи — один двигун: Ruby та JavaScript

Спільноти розробників різні, але болі у всіх однакові. Тому я портував TRE на дві потрібні мені мови розробки.

Ruby: tre_regex

В екосистемі Ruby для зв’язку з С-бібліотекою традиційно використовується FFI (Foreign Function Interface). Це дозволяє під капотом викликати компільований код без написання складних С-екстеншенів вручну.

Встановлення:

gem install tre_regex (чи через bundler)

Як це виглядає в коді:

require 'tre_regex'

# Створюємо регулярку, ігноруючи регістр
regex = TreRegex::Regex.new('apple', ignore_case: true)

# Дозволяємо рівно 1 помилку будь-якого типу (в даному випадку - видалення літери 'p')
result = regex.exec('I ate an aple', max_errors: 1)

puts result
# => {
#      match: "aple",
#      submatches: [],
#      index: 9,
#      end_index: 13,
#      cost: 1,
#      errors: {insertions: 0, deletions: 1, substitutions: 0}
#    }

Node.js: @tre-regex/regex

Для Node.js писати чисті С-біндінги в 2026 році — це вже майже моветон, коли є Rust. Тому Node.js-версія побудована на базі napi-rs, яка безпечно та ефективно прокидає TRE C-library через Rust-прошарок. Пакет постачається з прекомпільованими бінарниками під більшість архітектур, тому вам не доведеться ставити node-gyp та згадувати, де у вашій системі лежать заголовочні файли С

Встановлення:

npm install @tre-regex/regex

Як це виглядає в коді:

import { TreRegex } from "@tre-regex/regex";

const regex = new TreRegex("apple");

// Дозволяємо одну помилку
const result = regex.exec("I ate an aple", { maxErrors: 1 });

console.log(result.matchText); // => "aple"
console.log(result.index);     // => 9

Фічі, які роблять цей пошук «розумним»

Просто сказати «знайди мені щось схоже» — це шлях до хаосу. TreRegex дає вам хірургічно точні інструменти для керування цим хаосом.

Гранулярний контроль помилок

Ви можете гнучко налаштовувати, які саме гріхи ви готові прощати тексту, а які — ні. Для цього є чотири параметри (тут і далі приклади для Ruby бібліотеки, але API сумісне з node.js, просто у останнього параметри camelCase, в не snake_case):

• max_insertions — максимальна кількість зайвих символів у тексті (літера-паразит).
• max_deletions — максимальна кількість пропущених символів.
• max_substitutions — кількість символів, які замінили на інші.
• max_errors — загальний ліміт на суму всіх трьох операцій.

regex = TreRegex::Regex.new('library')

# Ми готові пробачити ОДНЕ видалення літери, але категорично проти замін та вставок
regex.exec('librry', max_deletions: 1, max_substitutions: 0, max_insertions: 0)
# => знайде "librry" (успіх!)

# А ось це поверне nil, бо 'lubrary' вимагає заміни літери 'i' -> 'u'
regex.exec('lubrary', max_deletions: 1, max_substitutions: 0, max_insertions: 0)
# => nil

Ціна помилки (Costs & Weights)

Іноді одні помилки є дешевшими за інші. Наприклад, при розпізнаванні OCR заміна літери O на нуль 0 або I на одиницю 1 — це звична справа, і за неї не варто сильно карати алгоритм. А ось поява абсолютно лівої літери має коштувати дорожче.

Ви можете налаштувати «штрафні бали» за кожну операцію:

# Задаємо загальний бюджет вартості помилок (max_cost: 2)
# Пропуск чи вставка літери коштує 1 бал, а ось заміна — аж 3 бали
options = {
  max_cost: 2,
  weight_deletion: 1,
  weight_insertion: 1,
  weight_substitution: 3
}

regex = TreRegex::Regex.new('algorithm')

# Маємо 1 видалення літери 'h'. Вартість = 1. (1 < 2, проходить)
regex.test?('algoritm', options) # => true

# Маємо 1 заміну літери 'i' -> 'e'. Вартість = 3. (3 > 2, штраф! Помилка занадто дорога)
regex.test?('algorethm', options) # => false

Fuzzy Capture Groups

Fuzzy Capture Groups (круглі дужки ()) повністю підтримуються і підкоряються загальним правилам «нечіткості». Якщо помилка сталася всередині дужок, то в масиві саб-метчів прилетить саме той кривий шматок тексту, який фактично збігся

regex = TreRegex::Regex.new('I ate an (apple)')
result = regex.exec('I ate an aple', max_errors: 1)

# Група розпізнала слово, попри помилку, і повернула те, що реально було в тексті
result[:submatches] # => ["aple"]

Маленьке технічне обмеження: через особливості алокації пам’яті в FFI/N-API діє суворий ліміт — максимум 9 capture-груп на один вираз. Усе, що ви напишете з 10-ї групи й далі, регулярка зматчить, але в масив результатів не покладе.

Підводні камені, або як не прострелити собі ногу

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

Феномен порожнього рядка (The «Empty Match»)

Якщо ви виставите максимальну кількість помилок (max_errors), яка дорівнює або перевищує довжину самого паттерна, алгоритм видасть математично логічний, але неочікуваний фінт.

Він вирішить: «Хм, якщо видалити з трилітерного слова „cat“ всі три літери, то вартість операції буде 3. Це вписується в ліміт. Значить, порожній рядок "" наприкінці тексту — це ідеальний збіг!».

regex = TreRegex::Regex.new('cat')
# Шукаємо з лімітом 3 помилки
regex.match_all('cot, cow', max_errors: 3).to_a
# => Поверне збіги для "cot", "cow" і порожній рядок "" наприкінці

Порада для розробника: Якщо вам потрібен високий загальний ліміт помилок, але ви хочете захиститися від порожніх збігів, завжди явно обмежуйте параметр max_deletions так, щоб принаймні частина слова була змушена «вижити»:

# Дозволяємо 3 помилки загалом, але забороняємо видаляти більше 2 літер під нуль
regex.match_all('cot, cow', max_errors: 3, max_deletions: 2).to_a
=> Поверне тільки ["cot", "cow"], пусті рядки заблоковано!

POSIX ERE замість PCRE

Ваш улюблений Oniguruma-рушій у Ruby чи V8 в Node.js підтримує купу сучасних штук: lookaheads, lookbehinds, backreferences тощо. Під капотом TreRegex працює стандарт POSIX Extended Regular Expressions (ERE). Тут є класи символів [a-z], квантифікатори *, +, ?, але немає жодних перлових розширень. Спроба згодувати вираз на кшталт cat(?=s) викличе помилку компіляції виразу.

Ціна екстремальної нечіткості, або як не перетворити прод на попелище

Нечіткий пошук за своєю природою є набагато «важчим» та обчислювально дорожчим для процесора, ніж класичний exact match. Алгоритм TRE масштабується залежно від двох ключових факторів: довжини вхідного рядка та кількості дозволених помилок.

Якщо ви вирішите нацькувати регулярку на величезний масив контенту (наприклад, завантажите туди текст цілої книги чи лог-файл розміром з білд-артефакт) і виставите ліміт max_errors: 10, рушій почне прораховувати таку астрономічну кількість розгалужень та комбінацій, що ваш процесор миттєво завантажиться на 100%, а кулери сервера зашумлять як реактивний літак перед зльотом

Порада для розробника: Тримайте ліміти помилок у розумних та реалістичних межах. Для більшості життєвих кейсів та виловлювання одруків чи дефектів OCR ідеально підходить значення від 1 до 3. Якщо ж вам дійсно потрібно дозволити величезну кількість помилок у великому документі, краще спочатку розбити вхідний текст на менші шматки (наприклад, по реченнях або окремих словах) перед тим, як згодовувати його TreRegex рушію

Безпека Unicode (Character Indices vs Byte Offsets)

У мові С будь-який рядок — це просто масив байтів. Якщо у вашому тексті є мультибайтні символи (наприклад, українські літери Ґ, Є, І займають 2 байти або емодзі 🍎, які займають по 4 байти), то стандартні С-бібліотеки повертають індекси зсуву в байтах. Якщо використати їх для звичайного слайсингу рядка в Ruby чи JS, ви поріжете текст по живому і отримаєте поломані символи.

TreRegex бере цей біль на себе. Під капотом відбувається прозорий мапінг байтових зсувів у нативні character індекси мови розробника.

regex = TreRegex::Regex.new('apple')
target = 'I ate 🍎 and an aple'

result = regex.exec(target, max_errors: 1)
# => Поверне index: 15, end_index: 19

# Це на 100% безпечно, індекси чітко відповідають символам!
target[result[:index]...result[:end_index]] # => "aple"

Як не порізати емодзі на шматки, або Безпека багатобайтних символів (Partial Multi-byte Character Matching)

Оскільки низькорівневий Сі-енджин TRE працює виключно з сирими байтами, під час нечіткого пошуку може статися логічна, але дуже болюча для продакшену штука. Алгоритм може вирішити «видалити» або «замінити» окремий байт всередині багатобайтного UTF-8 символу (наприклад, емодзі, ієрогліфа чи специфічної літери). У ванільному Ruby чи JS спроба відрізати шматок стрінга за таким невалідним байтовим зсувом закінчиться бітими символами, а метод .valid_encoding? видасть сумне false.

Щоб ваш текст не перетворювався на купу нечитабельних знаків питання, TreRegex «під капотом» автоматично відстежує, чи не розрізає межа знайденого збігу багатобайтну послідовність. Якщо рушій бачить такий розкол, він безпечно розширює межі збігу назовні, щоб повністю охопити весь валідний символ (codepoint). Ваші дані гарантовано залишаться консистентними.

regex = TreRegex::Regex.new('test')

# Двигун може спробувати зматчити частину байтів всередині 4-байтового емодзі яблука,
# але обгортка безпечно розширить збіг, щоб захопити весь символ цілком.
result = regex.exec('tes🍎', max_errors: 3)

puts result[:match] 
# => "tes🍎"

puts result[:match].valid_encoding? 
# => true

Коли банан ділиться тільки один раз: Перекриття у match_all (Overlapping Matches)

Коли ви використовуєте метод match_all, варто пам’ятати про базову логіку поведінки регулярних виразів: рушій «поглинає» (consumes) рядок у міру просування вперед. За замовчуванням, стандартні регулярки (і TRE зокрема) не повертають збіги, які перекривають один одного (overlapping matches).

Якщо ви спробуєте знайти підрядок "ana" у слові "banana", ви отримаєте рівно один збіг (перший "ana"). Щойно рушій обробив ці символи, він рухається далі до залишку рядка "na", де паттерна вже немає.

regex = TreRegex::Regex.new('ana')

# Поверне 1 збіг, а не 2
regex.match_all('banana').to_a
# => [{match: "ana", submatches: [], index: 1, end_index: 4, cost: 0, errors: {insertions: 0, deletions: 0, substitutions: 0}}]

Порада для розробника: Якщо ваша бізнес-логіка критично вимагає знайти абсолютно всі перекриття (наприклад, для складного біоінформаційного аналізу чи специфічних текстових маркерів), вам доведеться обійти це обмеження вручну — просто зсовуйте початковий індекс пошуку (starting index) вперед на 1 символ після кожного успішного знаходження збігу.

Висновок

Нечіткі регулярні вирази (fuzzy regex) — це специфічний інструмент, який потрібен не щодня, але у своїй ніші (OCR, аналіз брудних даних, лінгвістичний пошук) він економить сотні годин написання кастомних костилів.

Обидва проєкти повністю опенсорсні, опубліковані під ліцензією MIT і чекають на ваші зірочки або пулл-реквести:

• Ruby Gem: tre_regex на GitHub
• Node.js NPM Package: tre-regex на GitHub

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