Pergunta sobre regex, levenshtein-distance – Distância Levenshtein em expressão regular

9

Existe a possibilidade de incluir a distância levenshtein na consulta de expressão regular?

Exceto fazer união entre permutações. Como procurar "olá" com L.d. 1

<code>.ello | h.llo | he.lo | hel.o | hell.
</code>

isto é muito estúpido e não utilizável para números maiores de L.d.

Sua resposta

2   a resposta
5

Existe a possibilidade de incluir a distância levenshtein na consulta de expressão regular?

Não, não de uma maneira sensata. Implementar - ou usar um algoritmo de distância existente - Levenshtein é o caminho a percorrer.

ok, eu vou esperar se alguém vai responder, caso contrário eu vou marcar sua resposta como correta :-) zdenda.online
7

Você pode gerar o regex programaticamente. Vou deixar isso como um exercício para o leitor, mas para a saída dessa função hipotética (dada uma entrada de "palavra") você quer algo como essa string:

<code>"^(?>word|wodr|wrod|owrd|word.|wor.d|wo.rd|w.ord|.word|wor.?|wo.?d|w.?rd|.?ord)$"
</code>

Em inglês, primeiro tente corresponder à palavra em si, depois a cada transposição única possível, depois a cada inserção única possível, depois a cada omissão ou substituição individual possível (pode ser feita simultaneamente).

O comprimento dessa string, dada uma palavra de comprimento n, é linear (e notavelmente não exponencial) com n.

O que é razoável, eu acho.

Você passa isso para o seu gerador de regex (como em Ruby seria Regexp.new (str)) e bam, você tem um matcher para QUALQUER palavra com uma distância de Damerau-Levenshtein de 1 de uma determinada palavra.

(Distâncias Damerau-Levenshtein de 2 são muito mais complicadas.)

Observe o uso da construção (?> Non-backtracing, que significa a ordem das expressões individuais nessa questão de saída.

Eu não conseguia pensar em uma maneira de "compactar" essa expressão.

EDIT: eu tenho que trabalhar, pelo menos em Elixir!https://github.com/pmarreck/elixir-snippets/blob/master/damerau_levenshtein_distance_1.exs

Eu não recomendaria necessariamente isso (exceto para propósitos educacionais), já que isso só o levaria a distâncias de 1; uma biblioteca D-L legítima permitirá que você calcule distâncias> 1. Embora seja regex, provavelmente funcionaria bem rápido uma vez construído (observe que você deve salvar o regex "compilado" em algum lugar, pois este código o reconstrói em CADA comparação!)

Perguntas relacionadas