нечеткое сопоставление регулярных выражений в julia

Есть ли способ выполнить нечеткое сопоставление регулярных выражений в Джулии?

Я построил следующий тест регулярного выражения:

toMatch = Regex(word,"i")
ismatch(toMatch,input_string)

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

Я нашел пакет Levenshtein, который может рассчитать расстояние, но не уверен, как включить его в эту логику. Например:

levenshtein("hello","hllo")`
> 1

julia fuzzy-comparison
person Aaron    schedule 20.06.2016    source источник
comment
Вам нужно регулярное выражение здесь? Это звучит как сложная (в вычислительном отношении) проблема для общих регулярных выражений.   -  person Fengyang Wang    schedule 21.06.2016
comment
Возможно, что мне это не нужно. Сначала я решил эту проблему для точных совпадений, используя приведенный здесь код, а теперь пытаюсь разрешить принятие опечаток в input_string.   -  person Aaron    schedule 21.06.2016

Ответы (1)


arrow_upward
2
arrow_downward

(Этот ответ не имеет ничего общего с регулярными выражениями, но охватывает некоторые варианты использования.)

Я не знаю, работает ли это для вашего варианта использования. Но похоже, что вы пытаетесь найти, есть ли в вашем тексте слово (или близкая к нему опечатка). Если текст разделен пробелами, а ваше слово не содержит пробелов, вы можете попробовать что-то вроде:

nopunct(s) = filter(c -> !ispunct(c), s)
nfcl(s) = normalize_string(s, decompose=true, compat=true, casefold=true,
                              stripmark=true, stripignore=true)
canonicalize(s) = nopunct(nfcl(s))
fuzzy(needle, haystack, n) = any(
    w -> levenshtein(w, canonicalize(needle)) < n,
    split(canonicalize(haystack)))

Что это делает, примерно:

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

julia> nfcl("Ce texte est en français.")
"ce texte est en francais."

nopunct убирает знаки препинания, еще больше упрощая строку.

julia> nopunct("Hello, World!")
"Hello World"

canonicalize просто объединяет эти два преобразования.

Затем мы проверяем, находятся ли какие-либо слова в стоге сена (разделенные пробелами) в пределах n от иголки.

Примеры:

julia> fuzzy("Robert", "My name is robrt.", 2)
true

julia> fuzzy("Robert", "My name is john.", 2)
false

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

person Fengyang Wang    schedule 21.06.2016
comment
Это очень полезно, однако в моем случае слово, которое я пытаюсь найти в своем тексте, может содержать пробелы, поскольку это может быть фраза. Есть ли какие-либо модификации, которые вы могли бы предложить, которые можно было бы адаптировать? - person Aaron; 22.06.2016
comment
@Aaron Если игла представляет собой простую старую строку (без символов регулярного выражения, таких как * или ()), вы можете сделать трюк: вычислить levenshtein(needle, haystack) и проверить, меньше ли оно length(haystack) - length(needle) + n. (Чтобы добраться из стога сена до иголки, необходимо удалить не менее length(haystack) - length(needle) символов, а затем, возможно, до n дальнейших операций.) Это работает независимо от того, какие символы находятся в иголке. - person Fengyang Wang; 22.06.2016
comment
Я думаю, что это будет работать очень хорошо для моих нужд. Одна модификация, которую я добавлю, состоит в том, чтобы немного изменить n в зависимости от length of needle. - person Aaron; 22.06.2016
comment
Спасибо @FengyangWang. @ Аарон, хороший звонок. Я лично использовал fuzzy(needle, haystack, round(Int, length(needle) * (3/4))). - person Jake Ireland; 12.05.2021