JS: Text in Liste unscharf suchen

Folgendes Problem: Ich habe eine Liste von Dateien, in denen Einstellungsparameter gespeichert sind.

[
  "Hardcover 130g Premium matt.txt",
  "Hardcover 135g Bilderdruck glänzend.txt",
  "Hardcover 135g Bilderdruck matt.txt",
  "Softcover 100g Naturpapier matt.txt",
  "Softcover 120g Naturpapier matt.txt",
  "Softcover 130g Premium matt.txt",
  "Softcover 135g Bilderdruck glänzend.txt",
  "Softcover 135g Bilderdruck matt.txt"
]

Welche Datei verwendet werden soll, steht in einem Jobticket, aber ich kann nicht garantieren, dass da EXAKT der Name steht. Ich muss also auch mit „Softcover 120 g Naturpapier matt“ oder gar „Soft-Cover 120 g Natur matt“ rechnen.

Wie finde ich die richtige Datei?

Der Algorithmus

Es gibt wie immer verschiedene Methoden, an ein Problem ranzugehen; der Algorithmus, den ich kenne, nennt sich Levenshtein.

Wikipedia erklärt:

Die Levenshtein-Distanz zwischen zwei Zeichenketten ist die minimale Anzahl von Einfüge-, Lösch- und Ersetz-Operationen, um die erste Zeichenkette in die zweite umzuwandeln.

Die Wörter „Maus“ und „Haus“ haben also eine Distanz von 1, weil es reicht, das M gegen H zu tauschen.

„InDesign“ und „InCopy“ haben eine Distanz von 6: „Desi“ muss gegen „Copy“ getauscht werden und „gn“ muss gelöscht werden.

Die Implementation

Wie es im Englischen heißt: „Kopieren ist die ehrlichste Form des DiebstahlsKompliments“, also googelt man als erstes, was man an Doku und Beispiel-Code im Netz so finden kann.

Und da bin ich auf diesen exzellenten Beitrag in stackoverflow gestoßen, wo eine schwer optimierte Funktion zur Berechnung der Distanz veröffentlicht wurde.

Im ExtendScript-Kontext sieht das dann so aus:

var a = [
 "Hardcover 130g Premium matt.txt",
 "Hardcover 135g Bilderdruck glänzend.txt",
 "Hardcover 135g Bilderdruck matt.txt",
 "Softcover 100g Naturpapier matt.txt",
 "Softcover 120g Naturpapier matt.txt",
 "Softcover 130g Premium matt.txt",
 "Softcover 135g Bilderdruck glänzend.txt",
 "Softcover 135g Bilderdruck matt.txt"
];
var input = "120 Naturpapier";

// ------------------------------------------------------------------------------
// Nur den dichtesten finden
// ------------------------------------------------------------------------------
var min = 99999;
var min_ix = 0;

var then = new Date();
for ( var n = 0; n < a.length; n++) {
 var b = levDist( input, a[n] );
 if ( b < min ) { 
  min = b; 
  min_ix = n 
 }
}
var now = new Date();

$.writeln( [
 now.getTime() - then.getTime(),
 "min: " + min,
 "min_ix: " + min_ix,
 a[min_ix]
].join(" - ") );

$.writeln( "\n----------------------\n");

// ------------------------------------------------------------------------------
// Nach Entfernung sortieren
// ------------------------------------------------------------------------------
var rs = [];
var then = new Date();
for ( var n = 0; n < a.length; n++) {
 var d = levDist( input, a[n] );
 rs[n] = { d: d, ix: n };
}
rs.sort( function( a, b ) {
 return ( a.d - b.d ) / Math.abs( a.d - b.d );
} );
var now = new Date();

$.writeln( "Dauer: " + (now.getTime() - then.getTime() ) );
for ( var n = 0; n < rs.length; n++) {
 $.writeln( rs[n].d + ": " + a[ rs[n].ix ] );
}


// ------------------------------------------------------------------------------
// Der eigentliche Algorithmus
// ------------------------------------------------------------------------------
function levDist(w1, w2) {
  var d = []; //2d matrix

  // Step 1
  var n1 = w1.length;
  var n2 = w2.length;

  if (n1 == 0) return n2;
  if (n2 == 0) return n1;

  //Create an array of arrays in javascript (a descending loop is quicker)
  for (var i = n1; i >= 0; i--) d[i] = [];

  // Step 2
  for (var i = n1; i >= 0; i--) d[i][0] = i;
  for (var j = n2; j >= 0; j--) d[0][j] = j;

  // Step 3
  for (var i = 1; i <= n1; i++) {
    var w1_i = w1.charAt(i - 1);

    // Step 4
    for (var j = 1; j <= n2; j++) {

      //Check the jagged ld total so far
      if (i == j && d[i][j] > 4) return n1;

      var w2_j = w2.charAt(j - 1);
      var cost = (w1_i == w2_j) ? 0 : 1; // Step 5

      //Calculate the minimum
      var mi = d[i - 1][j] + 1;
      var b = d[i][j - 1] + 1;
      var c = d[i - 1][j - 1] + cost;

      if (b < mi) mi = b;
      if (c < mi) mi = c;

      d[i][j] = mi; // Step 6

      //Damerau transposition
      if (i > 1 && j > 1 && w1_i == w2.charAt(j - 2) && w1.charAt(i - 2) == w2_j) {
        d[i][j] = Math.min(d[i][j], d[i - 2][j - 2] + cost);
      }
    }
  }

  // Step 7
  return d[n1][n2];
}

Und das erzeugt die Ausgabe in der Konsole:

47  -  min: 20  -  min_ix: 4  -  Softcover 120g Naturpapier matt.txt

----------------------

Dauer: 48
20: Softcover 120g Naturpapier matt.txt
21: Softcover 100g Naturpapier matt.txt
26: Softcover 130g Premium matt.txt
26: Hardcover 130g Premium matt.txt
31: Softcover 135g Bilderdruck matt.txt
31: Hardcover 135g Bilderdruck matt.txt
35: Hardcover 135g Bilderdruck glänzend.txt
35: Softcover 135g Bilderdruck glänzend.txt

Sprich: Der erste Code-Schnipsel findet als dichtesten den 4. Eintrag in 47/1000 Sekunden mit einer Distanz von 20.

Der zweite Code-Schnipsel sortiert die Eingabeliste, so dass wahlweise das 0. Element als default genommen oder dieses noch gegen die folgenden veglichen werden kann.

Resümee

Ich dachte, das ist vielleicht für den einen oder anderen hilfreich.