Suchalgorithmus für Zahlenreihen

[philBerlin]

Hallo hallo,

ich suche einen Suchalgorithmus, der eine Zahlenreihe in einer anderen Zahlenreihe wiederfindet. Die Sache ist jedoch die, dass bestimmte Zahlen dazwischen liegen könnten. Nun könnte man diese Zahlen ja vorher filtern, allerdings sind diese Zahlen wichtig und müssen später wieder zugeordnet werden.

Ein Beispiel:

Ich suche folgende Zahlenreihe, hier mit Konstanten notiert:
x-y-z
in
a-b-c-d-e-f-x-y-z-g-h-i-j-k

x-y-z soll aber auch hier richtig identifiziert werden:
a-b-c-d-e-f-x-y-p-p-p-z-g-h-i-j-k

Diese Notation wäre x-y-[p]-z und soll ausdrücken, dass p beliebig oft oder gar nicht vorkommen könnte.

Würde ich p vorher filtern und es kommt diese Reihe...
a-b-c-d-e-f-x1-y1-p1-z1-g-h-x2-y2-p2-z2-i-j-k
...dann müsste noch eine Zuordnung erfolgen, die die p's wieder den jeweiligen x-y-z zuordnet, oder der Algorithmus ist so clever und erkennt die Struktur und ein Filtern und Zuordnen könnte man sich ersparen.

Als letztes wäre noch interessant zu wissen, wie man x-y-[p]-z notieren könnte, im Zusammenhang mit dem Suchalgorithmus. In einer Liste oder in einem Array kann ich ja keine Klammern ausdrücken.

Viele Grüße
Phil

 

[wagalaweia]

Moinsen!
Eine einfache Möglichkeit hierfür ist mit regular expressions auf strings zu arbeiten. Das ist zwar sicher langsamer als ein guter eigener Algorithmus, aber dafür super-flexibel. Beispiel:

import java.util.Arrays;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class IntSequenceFinder {
	
	public static int[] findSequence(int[] A, String sequence) {
		// convert the array to a string (speedup by StringBuffer for large arrays)
		StringBuffer sb = new StringBuffer();		
		for (int i : A) {
			sb.append(i);
			sb.append("_");
		}
		String Astr = sb.toString();
		System.out.println("array as string: " + Astr);
		
		// try to find the match		
		Matcher matcher = Pattern.compile(sequence).matcher(Astr);
		if (!matcher.find())
			return null;

		// get the last match only
		String findSeq = matcher.group();
		System.out.println("found match: " + findSeq);

		// build int[] from the match-string
		String[] matchNums = findSeq.split("_"); 
		int[] res = new int[matchNums.length];		
		for(int i=0; i<matchNums.length; i++) {
			res[i] = Integer.valueOf(matchNums[i]); 
		}

		return res;		
	}
	
	public static void main(String[] args) {
 
		int[] A = {1, 2, 0, 3, 0, 4, 15, 0, 0, 6, 132, 0};
		System.out.println("array to handle: " + Arrays.toString(A)); 
		
		// use _ as seperator for multi-digit-ints.
		// Important is a trailing seperator to not match e.g. number 67 for sequence ...6 instead of ...6_
		String sequence = "3_(0_)*4_(0_)*15_(0_)*6_";
		System.out.println("sequence to find: " + sequence);
		
		int[] result = findSequence(A, sequence);
		System.out.println("result: " + (result == null ? "no match" : Arrays.toString(result)));
	}
}

Kannst ja mal schauen, ob das geschwindigkeitsmäßig in Ordnung für deine Zwecke ist.

Ansonsten könntest du einfach die möglichen Startpunkte (also die erste Ziffer) suchen und dann für jeden der Startpunkte aus Schritt für Schritt schauen, ob an ihm eine gültige Kette (inklusive Zwischenzeichen) vollendbar ist.

Tschö!
waga

 

[philBerlin]

Hallo hallo,

super Sache das mit den regulären Ausdrücken. Hab mich gerade ein wenig damit beschäftigt, und das ist ja echt super praktikabel. Ich hatte vorher das ganze in einem eigenen Suchalgorithmus gepackt. Der kann zwar nur das eine Problem lösen, ist aber natürlich um einiges schneller. So eine Zahlenkette findet der Algorithmus im Nanosekundenbereich. Würde man das gleiche mit regular expression machen, dann benötigt er immerhin 8 ms, auf meiner Kiste. Dafür ist das ganze natürlich sehr viel mächtiger.

Viele Grüße
Phil