Caracteres curinga correspondentes - Matching wildcards

Na ciência da computação , um algoritmo para correspondência de curingas (também conhecido como globbing ) é útil na comparação de strings de texto que podem conter sintaxe de curinga . Os usos comuns desses algoritmos incluem interfaces de linha de comando , por exemplo, o shell Bourne ou linha de comando do Microsoft Windows ou editor de texto ou gerenciador de arquivos, bem como as interfaces para alguns mecanismos de pesquisa e bancos de dados. A correspondência de curingas é um subconjunto do problema de correspondência de expressões regulares e correspondência de strings em geral.

O problema

Um matcher curinga testa um padrão curinga p contra uma string de entrada s . Ele executa uma correspondência ancorada e retorna verdadeiro apenas quando p corresponde à totalidade de s .

O padrão pode ser baseado em qualquer sintaxe comum (consulte globbing ), mas os programadores do Windows tendem a discutir apenas uma sintaxe simplificada suportada pelo tempo de execução C nativo:

Nenhum caractere de escape é definido
Curingas: ?corresponde exatamente a uma ocorrência de qualquer caractere. *corresponde a muitas ocorrências arbitrárias (incluindo zero) de qualquer caractere.

Este artigo discute principalmente a formulação do Windows do problema, a menos que indicado de outra forma.

Definição

Declarado em índices baseados em zero, o problema de correspondência de curinga pode ser definido recursivamente como:

{\ displaystyle {\ begin {alinhados} m_ {00} & = (p_ {0} = t_ {0}) \\ m_ {0j} & = (p_ {j-1} = {\ text {'*'} }) \ land m_ {0, j-1} \\ m_ {i0} & = {\ text {false}} \\ m_ {ij} & = {\ begin {cases} m_ {i-1, j-1 } & {\ text {for}} \; p_ {i-1} = t_ {j-1} \ lor p_ {i-1} = {\ text {'?'}} \\ m_ {i, j- 1} \ lor m_ {i-1, j} & {\ text {for}} \; p_ {i-1} = {\ text {'*'}} \\ {\ text {false}} & {\ texto {para}} \; p_ {i-1} \ neq t_ {j-1} \ end {casos}} && \ quad {\ text {para}} \; 1 \ leq i \ leq | p |, 1 \ leq j \ leq | t |. \ end {alinhado}}}

onde m _ij é o resultado da correspondência do padrão p com o texto t truncado nos caracteres i e j , respectivamente. Esta é a formulação usada pelo algoritmo de Richter e o algoritmo Snippets encontrado na coleção de Cantatore. Esta descrição é semelhante à distância de Levenshtein .

Problemas relacionados

Problemas diretamente relacionados na ciência da computação incluem:

Correspondência de padrões com don't cares ou gaps, uma pesquisa de string não ancorada com apenas o equivalente de ?definido.
Correspondência de padrões com curingas, uma pesquisa de string não ancorada com o equivalente de ambos os curingas definidos. Tem um tempo de execução exponencial, a menos que um limite de comprimento seja fornecido no padrão de correspondência com a variante de curingas flexível.

História

Os primeiros algoritmos para correspondência de curingas frequentemente dependiam da recursão , mas a técnica foi criticada por motivos de desempenho e considerações de confiabilidade. Algoritmos não recursivos para correspondência de curingas ganharam preferência à luz dessas considerações.

Entre os algoritmos recursivos e não recursivos, as estratégias para realizar a operação de correspondência de padrões variam amplamente, conforme evidenciado entre a variedade de algoritmos de exemplo referenciados abaixo. Técnicas de desenvolvimento de caso de teste e otimização de desempenho foram comprovadamente utilizadas em certos algoritmos, particularmente aqueles desenvolvidos por críticos dos algoritmos recursivos.

Algoritmos recursivos

A recursão geralmente ocorre na correspondência, *quando há mais sufixos para correspondência. Esta é uma forma de retrocesso , também feita por alguns matchers de expressão regular.

Rich Salz ' wildmat algoritmo (sh-como sintaxe)
Algoritmo de Filip e algoritmo de Vignesh Murugesan
Algoritmo de Martin Richter (idêntico aos Snippets e relacionado ao algoritmo 7-zip)
Implementações de fnmatch da biblioteca C (suporte [...]e conjuntos de caracteres multibyte):
- BSD libc fnmatch de Guido van Rossum , também parte da libc da Apple
- Glibc fnmatch

A forma geral desses algoritmos é a mesma. Na recursão, o algoritmo divide a entrada em substrings e considera que uma correspondência ocorreu quando UMA das substrings retorna uma correspondência positiva. Para dowild("*X", "abcX"), seria avidamente chamar dowild("X", "abcX"), dowild("X", "bcX"), dowild("X", "cX")e dowild("X", "X"). Eles geralmente diferem por coisas menos importantes, como suporte para recursos, e por fatores mais importantes, como otimizações menores, mas altamente eficazes. Alguns deles incluem:

O sinal ABORT contra sobre-recursão (Lars Mathiesen 1991). Embora seja correto recursar ingenuamente por todo o resto das strings (padrão e texto) *e garantir que UMA das substrings retorne uma correspondência positiva, o tempo de execução torna-se exponencial para rejeitar uma correspondência com muitas *no texto. Lars Mathiesen altera o retorno para três classes, correspondência, não correspondência e ABORT (nenhuma correspondência possível para recursão de asterisco.) O valor ABORT é retornado quando o texto é consumido muito cedo ou quando outra correspondência de asterisco falhou, garantindo um desempenho linear em relação ao número de asteriscos. (A complexidade geral é adicionalmente quadrática em relação ao número de caracteres restantes para corresponder.) O wildmatch ABORT do Git / Rsync também cobre entradas inválidas. O novo uwildmat INN faz o mesmo.
Avanço do asterisco na recursão. Este ajuste wildmatch é relativamente menor. Aplica-se quando a recursão deseja corresponder a "* X" em "abcX": quando um asterisco é seguido por um literal como "X", é óbvio que apenas a última comparação com comprimentos iguais teria uma chance de produzir uma correspondência . Isso foi visto anteriormente em uwildmat em 2000 e mais implicitamente no fnmatch de van Rossum para FNM_PATHNAME.

O algoritmo de Martin Richter é uma exceção a esse padrão, embora a operação geral seja equivalente. On * ele recorre para aumentar qualquer um dos índices, seguindo a formulação de programação dinâmica do problema. A técnica "ABORT" também se aplica a ele. Em padrões típicos (conforme testado por Cantatore), é mais lento do que as implementações de chamada gananciosa.

Os algoritmos recursivos são em geral mais fáceis de raciocinar e, com a modificação ABORT, eles têm um desempenho aceitável em termos de complexidade de pior caso. Em strings sem *, eles levam um tempo de tamanho linear para string para corresponder, pois há uma relação um-para-um fixa.

Algoritmos não recursivos

Os seguintes são desenvolvidos por críticos dos algoritmos recursivos:

Algoritmo de correspondência curinga de Kirk J. Krauss , usado pela IBM
Coleção de algoritmos de correspondência curinga de Alessandro Cantatore
Matcher iterativo de Dogan Kurt e matcher NFA mais lento.
Algoritmo incorreto de Siler (falha MATCH("da*da*da*", "daaadabadmanda"))

O seguinte não é:

Algoritmo incorreto de Jack Handy (falha MATCH("*?", "xx"))

As funções iterativas acima implementam o retrocesso salvando um conjunto antigo de ponteiros de padrão / texto e revertendo para ele caso uma correspondência falhe. De acordo com Kurt, uma vez que apenas uma combinação bem-sucedida é necessária, apenas um desses conjuntos precisa ser salvo.

Além disso, o problema de correspondência de curinga pode ser convertido em correspondência de expressão regular usando uma abordagem ingênua de substituição de texto . Embora os matchers de expressão regular não recursivos, como a construção de Thompson, sejam menos usados na prática devido à falta de suporte de referência anterior, a correspondência de curinga em geral não vem com um conjunto de recursos igualmente rico. (Na verdade, muitos dos algoritmos acima têm suporte apenas para ?e *.) A implementação de Russ Cox do Thompson NFA pode ser modificada trivialmente para tal. O algoritmo nrgrep baseado em BDM de Gustavo Navarro fornece uma implementação mais simplificada com ênfase em sufixos eficientes. Consulte também expressões regulares § implementações .

Languages

In other projects