Um analisador Earley pode ser transformado em um analisador difuso semelhante ao Levenshtein Automata Algo for DFA?

10

Existe uma maneira de executar a análise difusa (aceita seqüências de caracteres mesmo com erros de digitação a uma certa distância de edição), com um DFA e um Autômato Levenshtein construído em tempo de execução da palavra de entrada. É possível fazer algo semelhante com um analisador Earley? Estou achando difícil entender o algoritmo, e muito menos responder a essa pergunta.

EnjoysMath
fonte
11
Bem, o PDA está fechado contra muitas operações com a NFA, portanto, isso deve ser possível em princípio. Adaptar Earley parece ser um exercício rotineiro, já que temos permissão para usar contadores em itens. Estou esquecendo de algo?
Raphael
@ Rafael Sim Esta é a idéia geral. Minha resposta é mais longa, pois é difícil avaliar o que os usuários sabem ou não.
babou 31/07/2015
plz cita uma definição ref / sketch para "Levenshtein Automata". conhece alguém que pode se qualificar, mas a qual você está se referindo?
vzn 31/07/2015

Respostas:

8

A resposta é sim. No entanto, eu não faria isso com um analisador Earley, porque existem outros mais simples com os mesmos recursos.

Basicamente, o analisador Earley pertence a uma família de analisadores gerais livres de contexto, que produz todos os analisadores possíveis para uma determinada sequência, quando a gramática é ambígua.

Existem duas maneiras (pelo menos) de entender esses analisadores:

  • como interpretação dinâmica de programação de um autômato de empilhamento correspondente à gramática na sequência de entrada;

  • como a construção da interseção da gramática com um autômato de estado finito.

Ao analisar uma única cadeia, o autômato de estado finito a ser considerado é um autômato linear que reconhece apenas a cadeia a ser analisada, um símbolo de cada vez (o número de estado é ). Se você aplicar a construção entre produtos de uma FA e uma CF garmmar (Bar Hillel, Perlis, Shamir, 1961), obterá uma nova gramática CF que é uma nova gramática que gera . O ponto interessante geralmente esquecido é que preserva as árvores de análise usadas por , até a renomeação não-terminal (devido ao produto cruzado).w|w|+1AGFL(A)L(G)FG

Portanto, se o FA gerar apenas sua sequência de entrada, a gramática gerará apenas essa sequência (se estiver em , caso contrário, gera o idioma vazio ). Além disso, ele o gera com todas as árvores de análise que poderia usar para gerá-lo.AFL(G)G

Essa gramática é o que geralmente é chamado de floresta de análise compartilhada , e todos os algoritmos gerais de análise de CF são uma versão mais ou menos otimizada da construção de produtos cruzados, seja CYK, Earley, LR ou LL generalizada ou outros. Então, tudo o que estou dizendo se aplica a eles também.F

Mas, como você vê, isso generaliza a análise de todo um conjunto regular, se alguém estiver interessado em fazer isso.

Essa é precisamente a sua pergunta. Você tem uma string . Você deseja analisá-lo até algumas variações definidas por um transdutor de estado finito, que no seu caso é um transdutor que produz todas as seqüências de caracteres dentro de uma determinada distância de edição de Levenshtein de (mas a origem do transdutor é imaterial). O conjunto dessas strings é um conjunto regular que pode ser definido por um FA, com transição ponderada que pode calcular a distância de edição de cada string.ww

Se você faz o produto cruzado com sua gramática , obtém uma gramática floresta de análise compartilhada que gera todas as seqüências de caracteres na interseção. Além disso, você obtém os pesos de algumas das regras para poder calcular a distância de edição de cada uma das seqüências aceitas.GF

Se desejável, isso pode ser usado para manter apenas as cordas com uma distância mínima.

No entanto, isso pode ser melhorado um pouco, pois a composição com máquinas de estados finitos é associativa.

Se você sempre usa o mesmo transdutor de estado finito, como é o caso da sua pergunta, o caminho certo a seguir é compor a Gramática e o transdutor (aqui o autômato de Levenshtein), independentemente da sequência de entrada. Isso fornece uma gramática ponderada que você pode usar para analisar a sequência de entrada . O problema é que a análise com a construção brutal de interseção fornece cordas a qualquer distância de Levenshtein, ou seja, .GwΣ

Seria fácil podar essa construção para obter o mesmo resultado de antes, mas a melhor maneira é uma construção de interseção mais controlada, como a organização de programação dinâmica usada pela maioria dos analisadores na literatura, incluindo Earley, e usá-la para evitar gerar regra inútil calculando distâncias e abortando qualquer caminho computacional quando exceder o limite desejado. A programação dinâmica também pode ser usada para calcular diretamente a floresta de análise (ou árvore de análise) da string que tem a menor distância da entrada.

babou
fonte
pense que isso é útil, mas também talvez "leia demais" a questão, então dizer algo como "essa é precisamente a sua pergunta" não pode ser realmente preciso. você fez uma pergunta bastante vaga, não formalizada estritamente, e (tentou?) formalizá-la. provavelmente há mais de uma maneira de formalizar a idéia um tanto vaga. pense que pode ser útil primeiro definir cuidadosamente o que as construções de Levenshtein DFA fazem (existem algumas conhecidas / investigadas, mas de qual estamos falando?) e depois explicar como esse conceito pode ser generalizado para as lâmpadas fluorescentes compactas.
vzn
11
Na verdade, dou formalizações diferentes, que se complementam. Existem sutilezas nas quais não entrei, como o uso exato de pesos no processo, que depende do resultado exato que você deseja obter. Meu objetivo não é apenas dar uma resposta que tenha pouco interesse em minha opinião, mas dar uma compreensão mais ampla do problema. A escolha da distância de edição usada é irrelevante, pois funciona para qualquer coisa que possa ser expressa com um transdutor de estado finito ponderado.
babou 31/07/2015