Guten Tag,
mir geht es nicht um den Code zum genannten Problem, sondern um eine kurze Erklärung, wie man eine Shift Liste wie im Folgenden erstellt. Habe schon so viel Zeit mit suchen im Internet verbracht, dass ich einfach mal nachfragen wollte, wie man diese Liste erstellt. Suffix und Last Tabelle sind hierbei völlig veständlich. Gesucht werden soll mithilfe des Boyer-Moore-Algorithmus ”
clggclglcclg“ in der Zeichenfolge ”cckvglckclggclglcclgc“.
Kannst du noch mal (etwas ausführlicher) beschreiben, wo genau du Verständnisschwierigkeiten hast? Das konnte ich bislang nicht so rauslesen…
Naja, das Problem ist, dass ich keine Ahnung habe, wie die Shift-Tabelle entsteht, bzw. welche Schritte man durchführen muss, um solch eine Shift Tabelle zu erstellen. In unserer Vorlesung ist die Rede von der sicheren Verschiebedistanz, aber was kann ich damit anfangen?
Am einfachsten wäre es, das anhand des Codes zu zeigen… Aber den willst du nicht, und ich will mir auch gerade keine Mühe machen, und einen erstellen… Patt!
Edit: Vielleicht hilft ja diese Methode schon beim Verständnisaufbau:
public static <T> Deque<T> rotate(final Deque<T> deque, final int shift) {
for (int i = 0; i < shift; i++) {
deque.offerFirst(deque.pollLast());
}
return deque;
}
public static void main(String[] args) {
Deque<String> d = new ArrayDeque<>(Arrays.asList("eins", "zwei", "drei"));
rotate(d, 1);
System.out.println("d = " + d);
}
Moin,
so entsteht die Suffix-/Shift-Tabelle (ich habe den Code von Wikipedia verwendet):
/* Java Program for Bad Character Heuristic of Boyer
Moore String Matching Algorithm */
import java.util.Arrays;
class AWQ {
final static int NO_OF_CHARS = 256;
/**
* Ist needle[position] bis needle[needle.size() - 1] ein Präfix von needle?
*/
boolean isPrefix(char[] needle, int position) {
for (int i = position, j = 0; i < needle.length; ++i, ++j) {
if (needle[i] != needle[j]) {
return false;
}
}
return true;
}
/**
* Gibt die maximale Länge der Teilzeichenfolge zurück, die bei position endet
* und ein Suffix ist. (Hilfsfunktion für Guter-Suffix-Regel)
*/
int suffixSize(char[] needle, int position) {
int size = 0, i = position, j = needle.length - 1;
while (i >= 0 && needle[i] == needle[j]) {
--i;
--j;
++size;
}
return size;
}
/**
* Erstellt die Sprungtabelle basierend auf den nicht übereinstimmenden
* Zeicheninformationen. (Schlechtes-Zeichen-Regel)
*/
int[] makeCharTable(char[] needle) {
int[] table = new int[NO_OF_CHARS];
Arrays.fill(table, needle.length);
for (int i = 0; i < needle.length - 1; ++i) {
table[needle[i]] = needle.length - 1 - i;
}
return table;
}
/**
* Erstellt die Sprungtabelle basierend auf dem Scanoffset, bei dem eine
* Nichtübereinstimmung auftritt. (Guter-Suffix-Regel)
*/
int[] makeOffsetTable(char[] needle) {
int[] table = new int[needle.length];
int lastPrefixPosition = needle.length;
for (int i = needle.length; i > 0; --i) {
if (isPrefix(needle, i)) {
lastPrefixPosition = i;
}
table[needle.length - i] = lastPrefixPosition - i + needle.length;
}
for (int i = 0; i < needle.length - 1; ++i) {
int size = suffixSize(needle, i);
table[size] = needle.length - 1 - i + size;
printRow(i, size, needle, table);
}
printRow(needle.length - 1, suffixSize(needle, needle.length - 1), needle, table);
return table;
}
/**
* Gibt den Index innerhalb der Zeichenfolge des ersten Auftretens vom
* spezifizierten Teilstring zurück. Wenn es sich nicht um einen Teilstring
* handelt, wird -1 zurückgegeben.
*/
int indexOf(char[] haystack, char[] needle) {
if (needle.length == 0) {
return 0;
}
int[] charTable = makeCharTable(needle);
int[] offsetTable = makeOffsetTable(needle);
for (int i = needle.length - 1, j; i < haystack.length; ) {
for (j = needle.length - 1; needle[j] == haystack[i]; --i, --j) {
if (j == 0) {
return i;
}
}
i += Math.max(offsetTable[needle.length - 1 - j], charTable[haystack[i]]);
}
return -1;
}
int index = 0;
void printRow(int i, int size, char[] needle, int[] offsetTable) {
System.out.println(i + "\t" + needle[i] + "\t" + size + "\t" + Arrays.toString(offsetTable));
index++;
}
@SuppressWarnings("unused")
char[] shift(char[] txt, int shift) {
for (int i = 0; i < shift; i++) {
char first = txt[0];
System.arraycopy(txt, 1, txt, 0, txt.length - 1);
txt[txt.length - 1] = first;
}
System.out.println("txt = " + Arrays.toString(txt));
return txt;
}
public static void main(String[] args) {
AWQ awq = new AWQ();
char[] haystack = "cckvglckclggclglcclgc".toCharArray();
char[] needle = "clggclglcclg".toCharArray();
System.out.println(awq.indexOf(haystack, needle));
}
}
Man beachte Zeile 72 und 74. Sie ergeben die Tabelle:
0 c 0 [11, 13, 14, 12, 13, 14, 15, 16, 17, 18, 19, 20]
1 l 0 [10, 13, 14, 12, 13, 14, 15, 16, 17, 18, 19, 20]
2 g 3 [10, 13, 14, 12, 13, 14, 15, 16, 17, 18, 19, 20]
3 g 1 [10, 9, 14, 12, 13, 14, 15, 16, 17, 18, 19, 20]
4 c 0 [7, 9, 14, 12, 13, 14, 15, 16, 17, 18, 19, 20]
5 l 0 [6, 9, 14, 12, 13, 14, 15, 16, 17, 18, 19, 20]
6 g 3 [6, 9, 14, 8, 13, 14, 15, 16, 17, 18, 19, 20]
7 l 0 [4, 9, 14, 8, 13, 14, 15, 16, 17, 18, 19, 20]
8 c 0 [3, 9, 14, 8, 13, 14, 15, 16, 17, 18, 19, 20]
9 c 0 [2, 9, 14, 8, 13, 14, 15, 16, 17, 18, 19, 20]
10 l 0 [1, 9, 14, 8, 13, 14, 15, 16, 17, 18, 19, 20]
11 g 12 [1, 9, 14, 8, 13, 14, 15, 16, 17, 18, 19, 20]
8
Wie die shift[i] - Spalte entsteht, konnte ich allerdings nicht herausfinden. Für mich ergibt die keinen Sinn…