Stringologins juveler

Jewels of Stringology: Text Algorithms är en bok om algoritmer för mönstermatchning i strängar och relaterade problem. Den skrevs av Maxime Crochemore och Wojciech Rytter och publicerades av World Scientific 2003.

Ämnen

De första ämnena i boken är två grundläggande strängsökningsalgoritmer för att hitta exakt matchande delsträngar , Knuth -Morris-Pratt-algoritmen och Boyer-Moore-strängsökningsalgoritmen . Den beskriver sedan suffixträdet , ett index för att snabbt slå upp matchande delsträngar och två algoritmer för att konstruera det. Andra ämnen i boken inkluderar konstruktionen av deterministiska finita automater för mönsterigenkänning, upptäckten av upprepade mönster i strängar, strängmatchningsalgoritmer med konstant rymd och förlustfri komprimering av strängar. Ungefärlig strängmatchning täcks av flera varianter inklusive redigeringsavstånd och det längsta vanliga följdproblemet . Boken avslutas med avancerade ämnen inklusive tvådimensionell mönstermatchning, parallella algoritmer för mönstermatchning, det kortaste vanligaste supersträngproblemet , parametriserad mönstermatchning och duplikatkoddetektering och Rabin-Karp-algoritmen .

Publik och mottagning

Boken är skriven för en publik som är bekant med algoritmdesign och analys, men inte nödvändigtvis bekant med strängalgoritmer. Recensenten Rolf Klein menar att denna målgrupp kan vara snäv, eftersom han bedömer boken som för svår för många studenter, men som inte ger lika mycket djup för experter som samma författares tidigare bok Text Algorithms (1994 ) .

Recensenten Shoshana Marcus skriver att de algoritmer som valts för att inkluderas i boken är "eleganta men ändå grundläggande" men att de ofta har förbisetts av mer allmänna algoritmläroböcker. Hon skriver att boken i sig bör bli en värdefull referens för forskare inom detta område, och att den även skulle kunna användas som komplement till grund- eller forskarutbildningsmaterial i algoritmer. Recensenten Ricardo Baeza-Yates menar att bokens utelämnande av parallellprogrammeringstekniker på bitnivå återspeglar dess fördom mot teoretiska snarare än praktiska metoder, men håller ändå med om dess lämplighet för forskarkurser.