Wie zu erkennen und ähnliche Muster zu analysieren wie Excel tut?

Question

Sie kennen die Funktionalität in Excel, wenn Sie 3 Reihen geben mit einem bestimmten Muster und ziehen Sie die Spalte den ganzen Weg hinunter Excel das Muster für Sie weiterhin versucht.

Beispiel:

Typ ...

• test-1
• test-2
• test-3

Excel wird es weiterhin mit:

• Test-4
• test-5
• Test-n ...

Same Werke für einige andere Muster wie Termine und so weiter.

Ich versuche, eine ähnliche Sache zu tun, aber ich mag auch mehr Ausnahmefälle wie behandeln:

• Test-blau-somethingelse
• Test-gelb-somethingelse
• Test-rot-somethingelse

Jetzt auf der Grundlage dieser Einträge Ich möchte sagen, dass das Muster:

• test- [DYNAMIC] -Etwas

Fahren Sie mit dem [DYNAMIC] mit anderen Farben ist ganz eine andere Sache, ich wirklich, dass gerade jetzt nicht. Ich bin vor allem bei der Erkennung der [DYNAMIC] Teile im Muster interessiert.

ich brauche, dies zu erkennen, aus einem großen Pool von Einträgen. Angenommen, Sie bekommen 10.000 Strings mit dieser Art von Mustern, und Sie möchten Gruppe dieser Strings basierend auf Ähnlichkeit und auch erkennen, welcher Teil des Textes ständig ändert ([DYNAMIC]).

Dokumentklassifikation kann in diesem Szenario sinnvoll sein, aber ich bin nicht sicher, wo ich anfangen soll.

UPDATE:

Ich habe vergessen zu erwähnen, dass auch dann ist es möglich, mehrere haben [DYNAMIC] Muster.

Wie zum Beispiel:

• test_ [DYNAMIC] 12 [Dynamic2]

Ich glaube nicht, es ist wichtig, aber ich habe vor, dies in .NET zu implementieren, aber jeder Hinweis über die Algorithmen zur Verwendung wäre sehr hilfreich.

Answer 1

Sobald Sie beginnen unter Berücksichtigung dynamischer Teile von Mustern der Form zu finden: <const1><dynamic1><const2><dynamic2>.... ohne weitere Annahmen dann würden Sie müssen die längste gemeinsame Teilfolge der Probe Strings Sie bereitgestellt haben. Zum Beispiel, wenn ich test-123-abc und test-48953-defg haben, dann würden die LCS test- und - sein. Die dynamischen Teile wären dann die Spalten zwischen dem Ergebnis der LCS. Sie könnten dann Ihren dynamischen Teil in einer geeigneten Datenstruktur suchen.

Das Problem der LCS von mehr als 2 Strings zu finden, ist sehr teuer, und dies würde der Engpass des Problems sein. Auf Kosten der Genauigkeit können Sie dieses Problem handhabbar machen. Zum Beispiel könnten Sie LCS zwischen allen Paaren von Strings und Gruppe zusammen Sätzen von Saiten mit ähnlichen LCS Ergebnissen führen. Dies bedeutet aber, dass einige Muster nicht richtig erkannt werden.

Natürlich all dies vermieden werden kann, wenn Sie weitere Einschränkungen für die Saiten verhängen können, wie Excel tut das nur Muster der Form <const><dynamic> zu ermöglichen scheint.

Answer 2

zu finden [dynamic] ist nicht so große Sache, Sie, dass mit 2 Strings tun - nur am Anfang und Ende beginnen, wenn sie nicht-Sein-Gleichen zu starten, tun das gleiche vom Ende, und voila - hast du deine [dynamic]

so etwas wie (Pseudo-Code - irgendwie):

String s1 = 'asdf-1-jkl';
String s2= 'asdf-2-jkl';
int s1I = 0, s2I = 0;
String dyn1, dyn2;
for (;s1I<s1.length()&&s2I<s2.length();s1I++,s2I++)
  if (s1.charAt(s1I) != s2.charAt(s2I))
    break;
int s1E = s1.length(), s2E = s2.length;
for (;s2E>0&&s1E>0;s1E--,s2E--)
  if (s1.charAt(s1E) != s2.charAt(s2E))
    break;
dyn1 = s1.substring(s1I, s1E);
dyn2 = s2.substring(s2I, s2E);

Über Ihre 10k Daten-Sets. Sie würden diese (oder vielleicht ein wenig mehr optimierte Version) mit jeder Kombination, um herauszufinden, Ihre patten anrufen müssen (10k x 10k Anrufe). und dann sortiert das Ergebnis durch das Muster (dh. speichert Anfang und das Ende und sortierte nach diesen Feldern)

Answer 3

Ich denke, was Sie brauchen, ist zu berechnen so etwas wie der Levenshtein Abstand , finden die in einem typischen diff-ähnlichen Algorithmus.

Gruppe ähnlicher Strings und dann in jeder Gruppe von ähnlichen Strings, indentify Sie den dynamischen Teil

Answer 4

Google Text & Tabellen könnten besser sein, als Excel für diese Art der Sache, es glaubt oder nicht.

Google hat große Datenmengen auf Mengen gesammelt - zum Beispiel des in dem Beispiel, das Sie es gaben erkennen würde, das blau, rot, gelb ... als Teil der Reihe ‚Farben‘. Es ist weit vollständige Mustererkennung als Excel so würde eine bessere Chance für das Muster fortgesetzt wird.