suffix array

akvarel

ähh...was? Ich habe das Gefühl, dass das eine Linguistik Aufgabe ist. Vielleicht solltest du dich etwas weniger kryptisch ausdrücken?

http://en.wikipedia.org/wiki/Suffix_array
Man findet so nur die linke Grenze, ich möchte aber die rechte Grenze finden.

Die codes müssen identisch sein, wie es in meinem Buch steht, aber ich habe es probiert und sie können nicht identisch sein. Ich habe mit Bedienung gespielt, aber hat nicht geholfen, ich weiss nicht was ich genau am Code ändern muss.

otze

Oh, wir kommen einer tatsächlich verwertbaren Aussage immer näher.

Lass uns mal gemeinsam einen verständlichen Frageprototyp erstellen:

"Ich beschäftige mich gerade mit Suffix Arrays und habe diesen Algorithmus von Wikipedia [link] gefunden. Ich brauche aber nicht den Anfang des Suffixes, sondern sein Ende. Wie muss ich den Algorithmus abwandeln, um dieses zu finden?"

den zweiten Satz deiner Antwort empfinde ich grammatikalisch und sinnlich immer noch als suboptimal. Von daher ist der Frageprototyp oben nur eine weiter eNachfrage, ob es das ist, was du meintest?

Wenn du die rechte Grenze brauchst, solltest du die Länge der Suffixe mit speichern.

pumuckl

Und das hat genau was mit Standard-C++ zu tun???

C++ Forumbot

Dieser Thread wurde von Moderator/in pumuckl aus dem Forum C++ (auch C++0x) in das Forum Rund um die Programmierung verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

akvarel

Ich brauche aber nicht den Anfang des Suffixes, sondern sein Ende.

Nein. Mit diesem Code finde ich die linke Grenze vom Suffix Array. zB
bei p= aca und text= acaaaacatat ist die Linke grenze
2 aaacatat@
3 aacatat@
4 acaaacatat@
5 acatat@
7 at@
...
11 tat@
Wir finden den Lp mit Hilfe dieser Code (1,10)->(1,6)->(1,4)->(3,4) Also Lp=4
Lp ist die Stelle in Array, wo das wort aca der Prefix des Wortes ist.

Jetzt müssen wir den Rp finden - die rechte grenze, wo aca auch der Prefix des Wortes ist. und hier ist es Rp=5. Aber ich verstehe der Code zum Finden vom Rp nicht.

Also falls ich das richtig verstanden hab, suchst du:
http://en.wikipedia.org/wiki/Longest_repeated_substring_problem

akvarel

Nein

https://www.mi.fu-berlin.de/wiki/pub/ABI/ExactMatchingWS11/exact.pdf
Seite 1011.
Searching

Da ist der Code nur fuer die linke grenze, aber keinen fuer die rechte Grenze. Da steht aber, dass der Code similar ist. Es kann aber doch nicht similar sein und ich habe alles moegliche versucht, aber ich bin nicht zur loesung gekommen.

Zweiter Versuch
Du musst in der Zeile mit der if Bedingung:

if p <= T suftab [M] then R = M; else L = M;

das <= in < ändern, danach steht in L dein Lp, also noch die Zeilen mit

Lp = R;

durch

Rp = L;

ersätzen.

Also in L steht Rp.

akvarel

Ich habe es probiert. Aber das hat nicht geklappt. Damn. Ich habe da dann den Fehler gebaut. Danke.=)

akvarel

Ich habe mir nachgeschaut.es geht nich,wie du sagst.im beispiel oben nach deiner code ist dann Rp
(1,11) M=6,aca<at also R=M
(1,6) M=4,aca<acaac..also R=M
(1,4)M=3 aca>aacat.. L=M
(3,4)und Rp=L Rp=3.also klappt nicht
Wenn man aber das zeichen <= in > veraendert.dann klappt es auch nicht weil dann L nach 6 rutscht und dann ist ales schon vorbei
Wo ist der fehler?

otze

Du hast den Algorithmus nicht verstanden. er kann dir niemals 5 liefern, weil "acatat" eben NICHT das gesuchte suffix ist. Lp und Rp sind nur die indizes die bei der Binären Suche nach "aca" verwendet werden.

in deinem Algorithmus ist Lp mit L und Rp mit R bezeichnet.

akvarel

in deinem Algorithmus ist Lp mit L und Rp mit R bezeichnet.

Eben nicht. L und R sind da, um Rp und Lp zu finden.

Also der Trick ist, wie du den Fall

p = T suftab [M]

behandelst. Sonst ist es eine einfache binäre Suche. Hier mal ein kurzes Beispeil (den Sonderfall das p nicht enthalten ist hab ich weggelassen):

#include <iostream>
int main(int argc, char **argv) {
	const char data[] = { 'a', 'a', 'b', 'c', 'c', 'd', 'e', 'e', 'e', 'f', 'z' };
	const size_t data_size = sizeof(data) / sizeof(data[0]);

	char p = 'c'; // Bereichssuche nach p
	int Lp, Rp;

	// suche erstes p
	int l = 0, m, r = data_size;
	while ( (r - l) > 1 ) {
		m = (l + r) / 2;
		if (data[m] < p) {
			l = m + 1;
		} else if (data[m] == p) {
			r = m;
		} else {
			r = m - 1;
		}
	}
	Lp = l;

	// suche "letztes" p
	//l = Lp;
	r = data_size;
	while ( (r - l) > 1 ) {
		m = (l + r) / 2;
		if (data[m] < p) {
			l = m + 1;
		} else if (data[m] == p) {
			l = m;
		} else {
			r = m - 1;
		}
	}
	Rp = r;

	std::cout << p << '\t' << Lp << ':' << Rp << '\n';

	return 0;
}

Damit dein Algorithmus funktioniert kannst du aber nur Strings der Länge p vergleichen (zum Beispiel Substrings), wie otze schon bemerkt hat.

akvarel

Vielen Dank fuer den Code, aber ich wollte nur den Pseudocode fuers Verstehen. Weil ich verstehe wieso die Suche von Lp und Rp uebereinsimmen. Sie koenen doch nicht fast identisch sein. Und im obigen Beispiel habe ich nie die Variante, dass
p==T suftab[M] ist
aca ist immer doch != T suftab[M] und deswegen wird diese Variante nicht behandelt und dann sind die code fuer Lp und Rp identisch und ich verstehe dann einfach nicht wieso hier Rp=5 ist.

bei p= aca und text= acaaaacatat ist die Linke grenze
2 aaacatat@
3 aacatat@
4 acaaacatat@
5 acatat@
7 at@
...
11 tat@

akvarel schrieb:

im obigen Beispiel habe ich nie die Variante, dass p==T suftab[M] ist...

in der PDF (Seite 1011) steht aber:

it follows that p matches a suffix Ti if and only if i = suftab [k] for some k ∈ [Lp , Rp ]

und da du im obigen Beispiel L_p=4 und R_p=5 haben möchtest gilt bei p="aca" und L_p=4 das p==T suftab[M].
Index 4 enthält aber folgenden Suffix:

4 acaaaacatat

also kannst du nur bis Länge p vergleichen. (oder ich hab was falsch verstanden)