Representação intermediária / de codificação para distância de Levenshtein

8

As frases:

A rápida raposa marrom pula sobre o cachorro preguiçoso [A]

e

A raposa marrom uick pula sobre o cachorro preguiçoso [B]

pode ser comparado usando o algoritmo Levenshtein Distance para determinar a similaridade, calculando o número mínimo de adições, exclusões ou substituições de um único caracter necessário para transformar A em B.

Estou interessado em saber se existe uma representação intermediária ou possivelmente um esquema de codificação para a distância de Levenshtein. Não para uso entre duas frases, mas apenas uma codificação aplicada a uma única frase, de modo que o índice de caracteres não afete as comparações.

Em B, o 'q' está faltando em comparação com A. Uma comparação de string normal corresponderia 'The 'e falharia 'uick brown fox...'apenas devido a um deslocamento de caractere único. A Distância Levenshtein poderia ser usada para compará-la com a frase original A para uma comparação mais perdoadora, mas no meu caso, não terei duas frases, apenas uma.

Então, estou procurando alguma maneira de codificar inequivocamente uma frase em pacotes de informações, pequenos átomos de verdade (estou pensando em um pacote por caractere?) Que mantêm uma ordem local e assim por diante, mas se alguns dos pacotes está errado, não afeta os caracteres posteriores.

Cada frase única deve mapear para uma e apenas uma única codificação / representação intermediária, Sets A'e B'. Calcular a distância de A e B de Levenshtein seria o mesmo que calcular a interseção de conjuntos A' = B'.

Como alternativa - se esse problema não tiver uma solução (e isso com certeza for mapeado para uma área de pesquisa bastante comentada, eu não ficaria surpreso), algum argumento / prova convincente de sua insolabilidade.

Jason Kleban
fonte
2
Talvez esteja faltando alguma coisa, mas parece que você deseja um código de correção de erros do bloco. en.wikipedia.org/wiki/Block_code
S Huntsman
Certamente parece que isso está no estádio, mas não sei como aplicaria isso aqui.
21710 Jason Keyban
Para contextualizar, gostaria de aplicar o conceito de cofre nebuloso, geralmente aplicado a medições biométricas, a senhas. Em vez de um conjunto de medidas, este seria um conjunto de verdades atômicas sobre uma sequência de texto.
Jason Kleban
Pensando mais sobre isso - estou tendo problemas para pensar em como aplicar os princípios dos códigos de correção de erros para resolver isso. O motivo é que as senhas são arbitrárias e selecionadas por um usuário, não ditadas. Mas talvez seja aplicável de uma maneira menos óbvia?
quer

Respostas:

14

De fato, há algumas pesquisas nesse sentido para a distância de edição com alguns resultados positivos e outros negativos. (Talvez eu não esteja entendendo a pergunta com precisão, tentarei responder a perguntas que sei responder.)

1

  • Ω(logn)n

  • 2O(lognloglogn)

n

Certamente há mais literatura nesse sentido, mas deixe-me saber primeiro se isso está próximo do que você quis dizer.

Alex Andoni
fonte
Esqueci de mencionar: se você estiver usando a distância de edição para informações biométricas, poderá dar uma olhada no <a href=" arxiv.org/abs/cs.CR/0602007"> neste artigo de Dodis, Ostrovsky, Reyzin e Smith </a>.
Alex Andoni
Na verdade, não é para informações biométricas. Acho intrigante o fato de os Vauzos Difusos funcionarem para biometria, mas não poderiam ser usados ​​para algo "mais simples", como uma sequência de texto.
Jason Kleban
Sua resposta é ótima, obrigado. Deixe-me pensar sobre isso e pesquisar ...
Jason Kleban
Sim, suas descrições estão no ponto - elas parecem certas. +50! Por curiosidade, minha aplicação pretendida é clara através da pergunta original e de nossos comentários?
Jason Kleban
Oi Alex, acho que o site tem um bug. Eu concedi a você os 50 pontos completos, mas recebo uma mensagem de que a resposta foi selecionada automaticamente - fornecendo apenas 25. Desculpe por isso.
precisa
5

Se a única coisa que pode acontecer é que os caracteres desapareçam, acho que você só precisa resolver o maior problema de subsequência comum . (Uma subsequência é uma generalização de uma substring: pode haver vários locais na subsequência em que o material foi removido da sequência maior, não apenas no início e / ou no final.)

Além disso, você já viu esta lista de métricas ?

Talvez eu esteja entendendo mal a sua declaração do problema, mas parece-me que se você definir com precisão como os erros podem ocorrer (exclusão, transposição etc.) e criar uma árvore de sufixos, será possível ter um algoritmo bem rápido depois de pagar o custo de memória e pré-processamento da construção da árvore de sufixos.

Aaron Sterling
fonte
Obrigado por isso! Você me mostrou algumas coisas novas a considerar.
Jason Kleban
Erros podem ocorrer como inserções, exclusões. Transposições e trocas seriam legais, mas são composições das inserções e exclusões básicas - caso isso facilite a satisfação.
precisa
1

Isso é apenas um pensamento, não uma solução, mas muito tempo para um comentário.

Seu conjunto / representação poderia ser um edifício alfabético da string?
Exemplo (para A):


1. Start with the empty string (^$) 
2. Insert a between 1st ^ and 1st $ (now: ^a$)
3. Insert b between 1st ^ and 1st a (now: ^ba$) 
4. Insert c between 1st ^ and 1st b (now: ^cba$) 
5. Insert d between 1st b and 1st a (now: ^cbda$) 
6. Insert d between 1st a and 1st ^ (now: ^cbdad$) 

e assim por diante...

Sua representação seriam as etapas que você executou para criar a sequência (em ordem alfabética):

O elemento {a, {1, ^}, {1, $}} representa a etapa 2, enquanto {d, {1, b}, {1, a}} representa a quinta etapa.

Desde que você faça isso alfabeticamente em cada caso, você pode ter algo que possa usar.

Um pensamento complementar: comece com cópias suficientes de cada letra "abcdd" (para os 4 primeiros) e depois acompanhe suas transposições para construir a string. Agora estamos passando vagamente para a teoria da permutação.

[BTW, é "pula", não "pula", caso contrário não há 's' - sim, eu sei que você nunca disse que era um pangram]

barrycarter
fonte
Primeiro de tudo, ideia interessante. ... E obrigado pela correção 'Jumps' - mudei o post de acordo.
precisa
Eu acho que uma solução não poderia ter um "quinto passo". A ordem não importa - os pacotes não podem ser fortemente vinculados entre si em pedidos ou referências - e se um pacote estiver errado / faltando?
precisa
0

Parece-me que sua coisa simples deve funcionar. Cada pacote contém a posição e o personagem, por exemplo

The = <1, T>, <2, h>, <3, e>

Então você compara o primeiro par de A com o primeiro par de B etc. Isso deve lhe dar Levenshtein.

Xodarap
fonte
Mas e se um caractere inicial da string estiver ausente, todos os pares posteriores seriam desativados por 1, certo? Se tirarmos 'q' em [B], então [B] é <u, 5>! = [A] é <u, 6>, [B] é <i, 6>! = [A ] 's <i, 7>
Jason Kleban
Dito de outra forma, se eu entendi sua sugestão corretamente, é equivalente à igualdade de string / sequência.
precisa
@ uosɐſ: o remetente saberia a ordem correta, certo? Eles enviariam <u, 6>; o receptor pode obtê-lo como o quinto pacote, mas, se conseguirem, saberão que é a sexta letra.
Xodarap 21/10/10
1
A idéia é que você crie um conjunto T (s) para cada sequência s e, em seguida, compare T (s1) e T (s2) como conjuntos para encontrar T (s1) -T (s2) por exemplo, e o número de elementos nessa diferença é a distância. Não existe o "remetente" e "receptor"
barrycarter