algorithme pour trouver le plus proche en utilisant la chaîne mêmes caractères

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

  •  21-08-2019
  •  | 
  •  

Question

Étant donné une liste L des chaînes de caractères n, et un qui est un moyen efficace de trouver la chaîne de caractères d'entrée S, la chaîne de caractères en L qui contient le plus de caractères qui existent dans S? Nous voulons trouver la chaîne en L qui est plus étroitement composé des lettres contenues dans S.

La réponse évidente est de boucle par toutes les chaînes de n et vérifiez combien de caractères dans la chaîne actuelle existent dans S. Cependant, cet algorithme sera exécuté fréquemment, et la liste L de chaîne n sera stockée dans une base de données ... boucle manuellement à travers toutes les chaînes de n aurait besoin de quelque chose comme grand-Oh de n * m ^ 2, où n est le nombre de chaînes en l, et m est la longueur maximale d'une chaîne en l, ainsi que le max longueur de S ... m dans ce cas est en fait une constante de 150.

Y at-il une meilleure façon qu'une simple boucle? Y at-il une structure de données, je peux charger les chaînes de n dans qui me donnerait la capacité de recherche rapide? Y at-il un algorithme qui utilise la méta-données pré-calculées sur chacune des chaînes de n qui exécuterait mieux qu'une boucle?

Je sais qu'il ya beaucoup de geeks là-bas qui sont dans les algorithmes. Alors, s'il vous plaît aider!

Merci!

Était-ce utile?

La solution

Si vous êtes après les sous-chaînes, un ou Trie Patrica Trie pourrait être un bon point de départ .

Si vous ne se soucient pas de l'ordre, à peu près le nombre de chaque symbole ou une lettre, je calcule l'histogramme de toutes les chaînes, puis les comparer avec l'histogramme de l'entrée. 

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

Cela réduira les coûts de plus le pré-traitement O(26 * m + n) une fois si l'on considère que la casse des lettres latines.

Si m est constante, vous pouvez interpréter l'histogramme comme 26 vectoriel de dimension sur une sphère de dimension 26 par unité normalisant. Ensuite, vous pouvez simplement calculer le Dot Product de deux vecteurs donnant le cosinus de l'angle entre les deux vecteurs, et cette valeur doit être proportionnelle à la similitude des chaînes.

En supposant m = 3, un alphabet de taille trois A = { 'U', 'V', 'W' } seulement, et la liste suivante des chaînes. 

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

Les histogrammes sont les suivantes. 

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

Un histogramme est normalisé à h = (x, y, z) h' = (x/r, y/r, z/r) avec r la norme euclidienne de l'histogramme h -. Qui est r = sqrt(x² + y² + z²) 

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

L'entrée S = "VVW" a l'histogramme hs = (0, 2, 1) et l'histogramme normalisé hs' = (0.000, 0.894, 0.447).

Maintenant, nous pouvons calculer la similitude des deux histogrammes et h1 = (a, b, c) la distance h2 = (x, y, z) euclidienne des deux histogrammes. 

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

Pour l'exemple, nous obtenons. 

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

Par conséquent "UVW" est le plus proche de "VVW" (petits chiffres indiquent la similarité plus).

En utilisant les histogrammes normalisés et h1' = (a', b', c') nous pouvons calculer h2' = (x', y', z') la distance que le produit scalaire des deux histogrammes. 

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

Pour l'exemple, nous obtenons. 

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

Encore une fois « UVW » est déterminé à être le plus proche de « VVW » (plus grand nombre indiquent la similarité plus élevée).

Les deux rendement version des nombres différents, mais les résultats sont toujours les mêmes. On pourrait également utiliser d'autres normes - distance Manhattan (norme L1) par exemple -. Mais cela ne changera les chiffres parce que les normes dans les espaces vectoriels de dimension finie sont toutes équivalentes

Autres conseils

Ce que vous voulez est un BK- arbre. Il est un peu unintuitive, mais très cool -. Et il permet de rechercher des éléments dans un seuil de distance levenshtein (édition) en O (log n)

Si vous vous souciez de la commande dans vos chaînes d'entrée, les utiliser comme il est. Si vous ne le faites pas, vous pouvez trier les caractères individuels avant de les insérer dans le BK-Tree (ou l'interrogation avec eux).

Je crois que ce que vous cherchez se trouve ici: logique floue basée Technique de recherche

Il est assez lourd, mais c'est ce que vous demandez. Il parle de similitudes de mots, et le caractère égarée. 

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

il me semble que l'ordre des caractères est pas important dans votre problème, mais vous recherchez « quasi-anagrammes » du mot S.

Si tel est le cas, alors vous pouvez représenter chaque mot dans l'ensemble L comme un tableau de 26 entiers (en supposant que votre alphabet a 26 lettres). Vous pouvez représenter S de la même comme un tableau de 26 entiers; maintenant pour trouver le meilleur match que vous exécutez une seule fois par l'ensemble L et de calculer une distance métrique entre le S-vecteur et le L-vecteur courant, mais vous voulez définir la distance du système métrique (euclidienne / somme des carrés ou Manhattan / somme des différences absolues). Cet algorithme est O (n) parce que les vecteurs ont des longueurs constantes.

Voici une fonction T-SQL qui travaille beaucoup pour moi, vous donne la distance d'édition:

Exemple: 

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

La fonction: 

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
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top