[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

pl.comp.programming

Czy ktos moglby mi wyjasnic ?

Jarod

6/19/2007 12:30:00 PM

Czesc
Mam problem ze zrozumieniem implementacji algorytmu Boyer-Moore:

Konkretnie to czytalem jak to dziala i ogolnie rozumiem sam algorytm
natomiast nie wiem co robi funkcja FindSuffix and BuildGoodSuffix.
Chodzi mi o dokladna implementacje sposobu przetwarzania tych tablic i tego
algorytmu na podstawie ktorego on wie, ze akurat wtedy trzeba zapisac skok o
4 itd. Krocej mowiac, to jesli ktos jest w stanie dopisac komentarze do
poszczegolnych petli i napisac co dokladnie maja one na celu bylbym bardzo
wdzieczny.

Rozumiem efekt dzialania tych funkcji tzn. dlaczego te wartosci musza byc
takie a nie inne... Ale nie rozumiem sposobu dochodzenia do nich.


Zalaczam kod w C#:

public class BoyerMoore
{
private int[] m_badCharacterShift;
private int[] m_goodSuffixShift;
private int[] m_suffixes;
private string m_pattern;

public BoyerMoore(string pattern)
{
/* Preprocessing */
m_pattern = pattern;
m_badCharacterShift = BuildBadCharacterShift(pattern);
m_suffixes = FindSuffixes(pattern);
m_goodSuffixShift = BuildGoodSuffixShift(pattern, m_suffixes);
}

private int[] BuildBadCharacterShift(string pattern)
{
int[] badCharacterShift = new int[256];

for (int c = 0; c < badCharacterShift.Length; ++c)
badCharacterShift[c] = pattern.Length;
for (int i = 0; i < pattern.Length - 1; ++i)
badCharacterShift[pattern[i]] = pattern.Length - i - 1;

return badCharacterShift;
}

private int[] FindSuffixes(string pattern)
{
int f = 0, g;

int patternLength = pattern.Length;
int[] suffixes = new int[pattern.Length + 1];

suffixes[patternLength - 1] = patternLength;
g = patternLength - 1;
for (int i = patternLength - 2; i >= 0; --i)
{
if (i > g && suffixes[i + patternLength - 1 - f] < i - g)
suffixes[i] = suffixes[i + patternLength - 1 - f];
else
{
if (i < g)
g = i;
f = i;
while (g >= 0 && (pattern[g] == pattern[g + patternLength - 1 -
f]))
--g;
suffixes[i] = f - g;
}
}

return suffixes;
}

private int[] BuildGoodSuffixShift(string pattern, int[] suff)
{
int patternLength = pattern.Length;
int[] goodSuffixShift = new int[pattern.Length + 1];

for (int i = 0; i < patternLength; ++i)
goodSuffixShift[i] = patternLength;
int j = 0;
for (int i = patternLength - 1; i >= -1; --i)
if (i == -1 || suff[i] == i + 1)
for (; j < patternLength - 1 - i; ++j)
if (goodSuffixShift[j] == patternLength)
goodSuffixShift[j] = patternLength - 1 - i;
for (int i = 0; i <= patternLength - 2; ++i)
goodSuffixShift[patternLength - 1 - suff[i]] = patternLength - 1 - i;

return goodSuffixShift;
}
}


Jarod



--
Wys3ano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta....
2 Answers

Jakub Debski

6/19/2007 1:01:00 PM

0

Jarod explained :
> Konkretnie to czytalem jak to dziala i ogolnie rozumiem sam algorytm
> natomiast nie wiem co robi funkcja FindSuffix and BuildGoodSuffix.
> Chodzi mi o dokladna implementacje sposobu przetwarzania tych tablic i tego
> algorytmu na podstawie ktorego on wie, ze akurat wtedy trzeba zapisac skok o
> 4 itd.

Je?eli nie pomaga w zrozumieniu debugger, to znaczy, ?e chyba nie do
konca rozumiesz zasade dzia3ania tego algorytmu i komentarze wiele nie
pomog?...
Tablice masz "ludzkim" jezykiem dobrze opisane w angielskiej Wikipedii.

Ewentualnie pomó? sobie googluj?c "boyer moore animation".

pozdrawiam
Jakub

geo

6/19/2007 1:15:00 PM

0

http://www.i-lo.tarnow.pl/edu/inf/utils/rozinf/pages...
http://www.i-lo.tarnow.pl/edu/inf/utils/rozinf/pages...