algoritmo para encontrar corda mais próximo utilizando mesmos personagens

StackOverflow https://stackoverflow.com/questions/859441

  •  21-08-2019
  •  | 
  •  

Pergunta

Dada uma lista L de cadeias de caracteres n, e uma cadeia de caracteres de entrada S, o que é uma forma eficiente de encontrar a cadeia de caracteres em L que contém a maioria dos personagens que existem em S? Queremos encontrar a string em L que é mais estreitamente composta das letras contidas S.

A resposta óbvia é percorrer todas as cadeias n e verificação para ver quantos caracteres na exist seqüência atual em S. No entanto, esse algoritmo será executado com freqüência, ea lista L de corda n serão armazenados em um banco de dados ... laço manualmente através de todas as cordas n exigiria algo como big-Oh de n * m ^ 2, onde n é o número de cordas em L, e m é o comprimento máximo de qualquer cadeia em L, bem como o max comprimento de S ... neste caso m é na verdade uma constante de 150.

Existe uma maneira melhor do que apenas um loop simples? Existe uma estrutura de dados que pode carregar os n cordas em que me daria FAST Search capacidade? Existe um algoritmo que usa os meta-dados pré-calculados sobre cada um dos n cordas que teria um melhor desempenho do que um loop?

Eu sei que há um monte de geeks lá fora, que são para os algoritmos. Então, por favor me ajude!

Obrigado!

Foi útil?

Solução

Se você é depois de substrings, um Trie ou Patrica trie pode ser um bom ponto de partida .

Se você não se importa com a ordem, apenas sobre o número de cada símbolo ou letra, eu calcular o histograma de todas as cadeias e, em seguida, compará-los com o histograma da entrada. 

               ABCDEFGHIJKLMNOPQRSTUVWXYZ
Hello World => ...11..1...3..2..1....1...

Isto irá reduzir os custos para O(26 * m + n) mais o pré-processamento, uma vez, se você considerar letras latinas única insensíveis ao caso.

Se m é constante, você poderia interpretar o histograma como um vetor dimensional 26 em uma esfera unitária 26 dimensional, normalizando-lo. Então você poderia apenas calcular a Dot produtos de dois vetores produzindo o cosseno do ângulo entre os dois vetores, e este valor deve ser proporcional à semelhança dos strings.

Assumindo m = 3, um A = { 'U', 'V', 'W' } alfabeto de apenas tamanho três, e a seguinte lista de strings. 

L = { "UUU", "UVW", "WUU" }

Os histogramas são os seguintes. 

H = { (3, 0, 0), (1, 1, 1), (2, 0, 1) }

Um histograma h = (x, y, z) é normalizado para h' = (x/r, y/r, z/r) com r a norma euclidiana do h histograma -. Que é r = sqrt(x² + y² + z²) 

H' = { (1.000, 0.000, 0.000), (0.577, 0.577, 0.577), (0.894, 0.000, 0.447) }

O S = "VVW" de entrada tem o hs = (0, 2, 1) histograma e o histograma hs' = (0.000, 0.894, 0.447) normalizada.

Agora podemos calcular a similaridade dos dois histogramas h1 = (a, b, c) e h2 = (x, y, z) como a distância euclidiana de ambos os histogramas. 

d(h1, h2) = sqrt((a - x)² + (b - y)² + (c - z)²)

Para o exemplo obtemos. 

d((3, 0, 0), (0, 2, 1)) = 3.742
d((1, 1, 1), (0, 2, 1)) = 1.414
d((2, 0, 1), (0, 2, 1)) = 2.828

Assim "UVW" está mais próximo "VVW" (números menores indicam maior similaridade).

Usando os histogramas normalizados h1' = (a', b', c') e h2' = (x', y', z') podemos calcular a distância que o produto escalar de ambos os histogramas. 

d'(h1', h2') = a'x' + b'y' + c'z'

Para o exemplo obtemos. 

d'((1.000, 0.000, 0.000), (0.000, 0.894, 0.447)) = 0.000
d'((0.577, 0.577, 0.577), (0.000, 0.894, 0.447)) = 0.774
d'((0.894, 0.000, 0.447), (0.000, 0.894, 0.447)) = 0.200

Again "UVW" está determinada a ser mais próximo "VVW" (números maiores indicam maior similaridade).

Ambos rendimento versão números diferentes, mas os resultados são sempre os mesmos. Pode-se também utilizar outras normas - Manhattan distância (L1 norma), por exemplo -. Mas isso só irá alterar os números, porque as normas em espaços vetoriais de dimensão finita são todos equivalentes

Outras dicas

Parece que você precisa de um trie . Tentativas são utilizados para pesquisar palavras semelhante à maneira como um corretor ortográfico vai funcionar. Então, se a string S tem os personagens da mesma ordem das Cordas em L, em seguida, isso pode funcionar para você.

Se, no entanto, a ordem dos caracteres em S não é relevante - como um conjunto de telhas scrabble e que pretende procurar a palavra mais longa - então esta não é a sua solução.

O que você quer é um BK- árvore . É um pouco unintuitive, mas muito legal - e que torna possível pesquisar por elementos dentro de um (edit) limiar de distância levenshtein em O (log n)

.

Se você se preocupa com ordenação em suas cadeias de entrada, usá-los como é. Se não o fizer você pode classificar os caracteres individuais antes de inseri-los no BK-Tree (ou consultar com eles).

Eu acredito que o que você está procurando pode ser encontrada aqui: Lógica fuzzy Based técnica de Pesquisa

É muito pesado, mas isso é o que você está pedindo. Ele fala sobre semelhanças de palavras e extravio personagem. 

i.e:

L I N E A R T R N A S F O R M
L I N A E R T R A N S F O R M
L E N E A R T R A N S F R M

parece-me que a ordem dos caracteres não é importante para o seu problema, mas você está à procura de "quase-anagramas" da palavra S.

Se é assim, então você pode representar cada palavra no conjunto L como um array de 26 inteiros (assumindo que o seu alfabeto tem 26 letras). Você pode representar S semelhante como um array de 26 inteiros; agora para encontrar o melhor jogo que você acabou de executar uma vez através do conjunto L e calcular uma métrica distância entre o S-vetor ea corrente L-vector, no entanto você deseja definir a distância métrica (por exemplo euclidiana / soma de quadrados ou Manhattan / soma das diferenças absolutas). Este algoritmo é O (n) porque os vectores têm comprimentos constantes.

Aqui está uma função T-SQL que tem vindo a trabalhar muito bem para mim, dá-lhe a distância de edição:

Exemplo: 

  SELECT TOP 1 [StringValue] , edit_distance([StringValue, 'Input Value')
    FROM [SomeTable]
ORDER BY edit_distance([StringValue, 'Input Value')

A Função: 

CREATE FUNCTION edit_distance(@s1 nvarchar(3999), @s2 nvarchar(3999))
RETURNS int
AS
BEGIN
  DECLARE @s1_len int, @s2_len int, @i int, @j int, @s1_char nchar, @c int, @c_temp int,
    @cv0 varbinary(8000), @cv1 varbinary(8000)
  SELECT @s1_len = LEN(@s1), @s2_len = LEN(@s2), @cv1 = 0x0000, @j = 1, @i = 1, @c = 0
  WHILE @j <= @s2_len
    SELECT @cv1 = @cv1 + CAST(@j AS binary(2)), @j = @j + 1
  WHILE @i <= @s1_len
  BEGIN
    SELECT @s1_char = SUBSTRING(@s1, @i, 1), @c = @i, @cv0 = CAST(@i AS binary(2)), @j = 1
    WHILE @j <= @s2_len
    BEGIN
      SET @c = @c + 1
      SET @c_temp = CAST(SUBSTRING(@cv1, @j+@j-1, 2) AS int) +
        CASE WHEN @s1_char = SUBSTRING(@s2, @j, 1) THEN 0 ELSE 1 END
      IF @c > @c_temp SET @c = @c_temp
      SET @c_temp = CAST(SUBSTRING(@cv1, @j+@j+1, 2) AS int)+1
      IF @c > @c_temp SET @c = @c_temp
      SELECT @cv0 = @cv0 + CAST(@c AS binary(2)), @j = @j + 1
    END
    SELECT @cv1 = @cv0, @i = @i + 1
  END
  RETURN @c
END
Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top