BNDM Algorithmus < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 20:47 Di 03.05.2016 | | Autor: | j3ssi |
| Aufgabe | Erweitern Sie den BNDM, dass die Worst-case Laufzeit nur noch $O(m + n [mm] \cdot \lceil [/mm] m/W [mm] \rceil [/mm] )$ beträgt. Der Algorithmus in phyton Code ist unten zu sehen. Es ist eine bitparallele Simulation eines NFA zum Pattern Matching.
|P|=m; |T|=n
1 def bndm(P, T): #P Pattern T Text
2 S, m, n = set(P + T), len(P), len(T)
3 [mm] A_0, [/mm] last = (1 << m) - 1, m
4 accept = 1 << (m - 1)
5 mask = create_masks(P[::-1], S) #rev. pattern
6 while last <= n:
7 A, j, lastsuffix = [mm] A_0, [/mm] 1, 0
8 while A:
9 A &= mask[T[last - j]]
10 if A & accept:
11 if j == m:
12 yield last - m, last; break
13 else: lastsuffix = j
14 j, A = j + 1, A << 1
15 last += m - lastsuffix
1 def create_masks(P, S):
2 mask = {s: 0 for s in S}
3 for i, c in enumerate(P):
4 mask[c] |= 1 << i
5 return mask |
Der momentan oben stehende Algorithmus hat so wie ich das sehe eine Worst-Case Laufzeit im Falle, dass das Pattern und der Text aus demselben Buchstaben bestehen von $O(m+nm [mm] \lceil [/mm] m/w [mm] \rceil [/mm] )$ wobei W die Wortgrösse ist.
Die Laufzeit kommt zustande dadurch, dass die bitweisen Operationen in Zeit [mm] $O(\lceil [/mm] m/W [mm] \rceil)$ [/mm] abgearbeitet werden können.
Die while Schleife in Zeile 8 wird im Worst Case Fall $O(m)$ mal aufgerufen wird. Die äussere While Schleife wird im WorstCase Fall $O(n)$ mal betreten. Die $O(m)$ kommen vom Kreieren der Masken.
Ich weiss nicht genau wo ich Ansetzen muss, um die geforderte Laufzeitreduktion hinzubekommen. Am ehesten würde ich sagen, dass
ih irgendwie die while Schleife um A einstapfen muss
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:20 Do 05.05.2016 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
