Je travaille sur une implémentation de recherche floue et dans le cadre de la mise en œuvre, nous utilisons Stringutils.getvenshteinDistance d'Apache. Pour le moment, nous allons pour une période de réponse moyenne maximale spécifique pour notre recherche floue. Après diverses améliorations et avec un profilage, le lieu où le plus de temps est dépensé consiste à calculer la distance de Levenshtein. Il prend environ 80-90% du temps total sur les cordes de recherche trois lettres ou plus.
Maintenant, je sais qu'il y a quelques limitations à ce qui peut être fait ici, mais j'ai lu des questions précédentes et sur le Wikipedia Link pour DD que si l'on veut limiter le seuil à une distance maximale définie, cela pourrait aider à réduire le temps passé sur l'algorithme, mais je ne sais pas comment faire cela exactement. P>
Si nous ne sommes intéressés que par le distance si elle est plus petite qu'un seuil k, alors il suffit de calculer une bande diagonale de largeur 2K + 1 dans la matrice. De cette façon, le l'algorithme peut être exécuté dans O (kl) temps, où l est la longueur des plus courtes chaîne. [3] p> BlockQuote>
Ci-dessous, vous verrez le code LH d'origine de Stringutils. Après c'est ma modification. J'essaie de calculer essentiellement les distances d'une longueur définie du I, J Diagonal (Donc, dans mon exemple, deux diagonales au-dessus et au-dessous de I, J Diagonal). Cependant, cela ne peut pas être correct comme je l'ai fait. Par exemple, sur la diagonale la plus élevée, il va toujours choisir la valeur de la cellule directement au-dessus, ce qui sera 0. Si quelqu'un pouvait me montrer comment rendre cela fonctionnel comme je l'ai décrit, ou certains conseils généraux sur la façon de le faire. , Ce serait vivement apprécié. p>
xxx pré> Mes modifications (uniquement sur les boucles pour les boucles): p>
xxx pré> p>
6 Réponses :
J'ai écrit à propos de Levenshtein Automata, qui sont une façon de faire ce type d'enregistrement dans O (n) Time avant, ici . Les échantillons de code source sont en python, mais les explications devraient être utiles et les documents référencés offrent plus de détails. P>
Cela semble être utile, mais j'essaie actuellement de voir quelle différence qu'un seuil ferait, car je ne suis pas sûr combien de temps j'aurai à ce sujet.
De plus, nous sommes assez proches d'atteindre notre marque souhaitée, alors un changement quelque peu petit serait plus agréable qu'un grand.
Comme vous l'avez dit dans la question initiale, si vous avez un seuil, cela prendra le temps O (n) au lieu de O (mn). La modification de la procédure de programmation dynamique pourrait bien être plus simple dans votre cas, mais je ne sais pas comment vous alliez à ce sujet.
ici quelqu'un répond une question très similaire:
CITE: B> juste la partie principale, plus de code dans l'original p> p>
Je l'ai fait plusieurs fois. La façon dont je le fais est avec une première marche de profondeur récursive de l'arbre de jeu des changements possibles. Il y a un budget k de changements que j'utilise pour tailler l'arbre. Avec cette routine à la main, je l'exécute d'abord avec k = 0, puis k = 1, puis k = 2 jusqu'à ce que je reçois un coup ou que je ne veux pas aller plus haut.
i> p>
J'ai utilisé le code d'origine et place ceci juste avant la fin de la boucle J pour la boucle:
if (p[n] > s.length() + 5) break;
Selon "Gusfield, Dan (1997). Algorithmes sur des cordes, des arbres et des séquences: informatique et biologie informatique" (page 264) Vous devez ignorer les zéros. P>
Le problème avec la mise en œuvre de la fenêtre traite de la valeur à gauche de la première entrée et au-dessus de la dernière entrée de chaque ligne.
Un moyen est de démarrer les valeurs que vous remplissez initialement à 1 au lieu de 0, puis ignorez tous les 0 à vous que vous rencontrez. Vous devrez soustraire 1 de votre réponse finale. P>
Un autre moyen est de remplir les entrées à gauche de la première et supérieure à des valeurs élevées afin que le contrôle minimum ne les choisira jamais. C'est comme ça que j'ai choisi quand je devais l'implémenter l'autre jour: p>
N'en a plus besoin, mais merci d'avoir fourni cette solution. C'était ce que je cherchais.
J'ai essayé ce code pour "ABCDE" et "XXCDE" qui calcule correctement une distance de LEVENSHTEINE 2. mais si je passe 1 comme seuil, votre méthode est censée répondre -1 comme le seuil réel est plus grand, non? En tout cas, il continue de répondre 2. Sauf si je ne passe pas 0 pour seuil. De toute façon, il est beaucoup plus rapide que la mise en œuvre par défaut!
Apache Commons Lang 3.4 a cette implémentation:
/** * <p>Find the Levenshtein distance between two Strings if it's less than or equal to a given * threshold.</p> * * <p>This is the number of changes needed to change one String into * another, where each change is a single character modification (deletion, * insertion or substitution).</p> * * <p>This implementation follows from Algorithms on Strings, Trees and Sequences by Dan Gusfield * and Chas Emerick's implementation of the Levenshtein distance algorithm from * <a href="http://www.merriampark.com/ld.htm">http://www.merriampark.com/ld.htm</a></p> * * <pre> * StringUtils.getLevenshteinDistance(null, *, *) = IllegalArgumentException * StringUtils.getLevenshteinDistance(*, null, *) = IllegalArgumentException * StringUtils.getLevenshteinDistance(*, *, -1) = IllegalArgumentException * StringUtils.getLevenshteinDistance("","", 0) = 0 * StringUtils.getLevenshteinDistance("aaapppp", "", 8) = 7 * StringUtils.getLevenshteinDistance("aaapppp", "", 7) = 7 * StringUtils.getLevenshteinDistance("aaapppp", "", 6)) = -1 * StringUtils.getLevenshteinDistance("elephant", "hippo", 7) = 7 * StringUtils.getLevenshteinDistance("elephant", "hippo", 6) = -1 * StringUtils.getLevenshteinDistance("hippo", "elephant", 7) = 7 * StringUtils.getLevenshteinDistance("hippo", "elephant", 6) = -1 * </pre> * * @param s the first String, must not be null * @param t the second String, must not be null * @param threshold the target threshold, must not be negative * @return result distance, or {@code -1} if the distance would be greater than the threshold * @throws IllegalArgumentException if either String input {@code null} or negative threshold */ public static int getLevenshteinDistance(CharSequence s, CharSequence t, final int threshold) { if (s == null || t == null) { throw new IllegalArgumentException("Strings must not be null"); } if (threshold < 0) { throw new IllegalArgumentException("Threshold must not be negative"); } /* This implementation only computes the distance if it's less than or equal to the threshold value, returning -1 if it's greater. The advantage is performance: unbounded distance is O(nm), but a bound of k allows us to reduce it to O(km) time by only computing a diagonal stripe of width 2k + 1 of the cost table. It is also possible to use this to compute the unbounded Levenshtein distance by starting the threshold at 1 and doubling each time until the distance is found; this is O(dm), where d is the distance. One subtlety comes from needing to ignore entries on the border of our stripe eg. p[] = |#|#|#|* d[] = *|#|#|#| We must ignore the entry to the left of the leftmost member We must ignore the entry above the rightmost member Another subtlety comes from our stripe running off the matrix if the strings aren't of the same size. Since string s is always swapped to be the shorter of the two, the stripe will always run off to the upper right instead of the lower left of the matrix. As a concrete example, suppose s is of length 5, t is of length 7, and our threshold is 1. In this case we're going to walk a stripe of length 3. The matrix would look like so: 1 2 3 4 5 1 |#|#| | | | 2 |#|#|#| | | 3 | |#|#|#| | 4 | | |#|#|#| 5 | | | |#|#| 6 | | | | |#| 7 | | | | | | Note how the stripe leads off the table as there is no possible way to turn a string of length 5 into one of length 7 in edit distance of 1. Additionally, this implementation decreases memory usage by using two single-dimensional arrays and swapping them back and forth instead of allocating an entire n by m matrix. This requires a few minor changes, such as immediately returning when it's detected that the stripe has run off the matrix and initially filling the arrays with large values so that entries we don't compute are ignored. See Algorithms on Strings, Trees and Sequences by Dan Gusfield for some discussion. */ int n = s.length(); // length of s int m = t.length(); // length of t // if one string is empty, the edit distance is necessarily the length of the other if (n == 0) { return m <= threshold ? m : -1; } else if (m == 0) { return n <= threshold ? n : -1; } if (n > m) { // swap the two strings to consume less memory final CharSequence tmp = s; s = t; t = tmp; n = m; m = t.length(); } int p[] = new int[n + 1]; // 'previous' cost array, horizontally int d[] = new int[n + 1]; // cost array, horizontally int _d[]; // placeholder to assist in swapping p and d // fill in starting table values final int boundary = Math.min(n, threshold) + 1; for (int i = 0; i < boundary; i++) { p[i] = i; } // these fills ensure that the value above the rightmost entry of our // stripe will be ignored in following loop iterations Arrays.fill(p, boundary, p.length, Integer.MAX_VALUE); Arrays.fill(d, Integer.MAX_VALUE); // iterates through t for (int j = 1; j <= m; j++) { final char t_j = t.charAt(j - 1); // jth character of t d[0] = j; // compute stripe indices, constrain to array size final int min = Math.max(1, j - threshold); final int max = (j > Integer.MAX_VALUE - threshold) ? n : Math.min(n, j + threshold); // the stripe may lead off of the table if s and t are of different sizes if (min > max) { return -1; } // ignore entry left of leftmost if (min > 1) { d[min - 1] = Integer.MAX_VALUE; } // iterates through [min, max] in s for (int i = min; i <= max; i++) { if (s.charAt(i - 1) == t_j) { // diagonally left and up d[i] = p[i - 1]; } else { // 1 + minimum of cell to the left, to the top, diagonally left and up d[i] = 1 + Math.min(Math.min(d[i - 1], p[i]), p[i - 1]); } } // copy current distance counts to 'previous row' distance counts _d = p; p = d; d = _d; } // if p[n] is greater than the threshold, there's no guarantee on it being the correct // distance if (p[n] <= threshold) { return p[n]; } return -1; }
La pensée vient de me faire valoir que je pouvais vérifier si la valeur est zéro puis l'ignore ou le remplace par une valeur arbitraire élevée. Devrait probablement penser à cela un peu plus, cependant.