Gibt es einen Algorithmus für die unscharfe Suche wie Levenshtein Distance für eine Reihe von geordneten Zeichen spezialisiert?

Question

Ich fand einen Algorithmus (auf https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance) und nachdem ich etwas mehr über Levenshtein gelesen hatte, verstand ich, dass es einen besseren Weg geben sollte, die Bearbeitungsdistanz von zwei Strings zu bestimmen, wenn diese Strings streng aus ascii-aphabetisch geordneten und einzigartigen Zeichen zusammengesetzt sind.

Bedeutung, für jedes a und b wie ein < b, wird ein vor sein b, und das gegenseitige (oder contraposed oder ich kann mich nicht erinnern) für jedes a, b und c wie ein < b < c Wenn eine Zeichenkette ac liest und die andere ab, dann weiß man, dass die erste nicht das b enthält.

Und das bedeutet genau, dass es eine bessere Möglichkeit gibt, den Bearbeitungsabstand zwischen zwei Saiten dieser Art zu bestimmen.

Wenn es nützlich ist, ist die Klasse, die ich verwende, um meine Charaktere zu organisieren, ein TreeSet of Character.

Answer 1

Dies ist die Lösung, die ich kam mit: ich es mit Werten verwendet: String getestet, String Ziel, 1, 0.

/** returns the cost of the difference between a tested CharSequence and a target CharSequence. CS = CharSequence 
* @param tested input, the CS which will be compared to the target. all letters sorted by ASCII order and unique 
* @param target is the CS to which the tested will be compared. all letters sorted by ASCII order and unique 
* @param positiveDifferenceCost is the cost to add when a letter is in the tested CS but not in the target. 
* @param negativeDifferenceCost is the cost to add when a letter is in the target CS but not in the tested. 
* @return int the number of differences. 
*/ 


public static int oneSidedOAUDistance(final CharSequence tested, final CharSequence target, 
             final int positiveDifferenceCost, final int negativeDifferenceCost) { 
    int diffCount = 0; 
    int index_tested = 0; 
    int index_target = 0; 

    if (positiveDifferenceCost == 0 && negativeDifferenceCost == 0) 
     return 0; 


    for (; index_tested < tested.length() && index_target < target.length();) { 
     if (tested.charAt(index_tested) == target.charAt(index_target)) { 
      ++index_tested; 
      ++index_target; 
      continue; 
     } 
     if (tested.charAt(index_tested) < target.charAt(index_target)) { 
      //some letters should not be there in tested string. 
      diffCount+= positiveDifferenceCost; 
      index_tested++; 

     } else { 
      //some letters miss in tested string. 
      diffCount+=negativeDifferenceCost; 
      index_target++; 
     } 
    } 


    return diffCount; 
}