Reviews for Flexible Pattern Matching in Strings: Practical on-Line Search Algorithms for Texts and Biological Sequences

The average rating for Flexible Pattern Matching in Strings: Practical on-Line Search Algorithms for Texts and Biological Sequences based on 2 reviews is 4.5 stars.

Review # 1 was written on 2007-12-03 00:00:00 Matthew Valva There is no better collection of state-of-the-art multipattern matching algorithms, and certainly no better review of the quite recent bit-parallel approaches (such as the Shift-OR algorithm of Baeza-Yates). Old favorites such as [Advanced] Aho-Corasick (with a detailed construction of its DFA and δ-function) and Backward Oracle / Backward Nondeterministic Dawg are covered and related, and the regex chapter's development of the Glushkov and Thompson automata is not unacceptable. Matching with errors has come a long way since Navarro hit his pattern-matching peak in 2001 or so (FPMiS was published 2002, but largely culled from previous journal articles) -- anyone looking for fuzzy matching would do well to look into recent bioinformatics research. The Wu-Manber coverage is far more readable than that team's original literature (see Wu 1994 and 1996). The fourth chapter is a gem for practitioners, introducing several low-cost partial solutions to multiple regex matching in a DFA or bit-parallel approach (these techniques will. admittedly. be trivially derived by any competent theorist). More fleshing-out of time- and space-costs, especially for wider sets of more diverse inputs, would be a fine addition. Average-case analyses are presented unrigorously -- not merely sans proof, but without even contextual specification. The book is sorely in need of detail regarding the memory profiles of these algorithms, beyond the occasional, trite "state fits into cache". Especially when performing exact multimatch on irregularly-quantized data, and especially with modern encodings, the memory-intensive automata approaches provide a keenly elegant computational model, flexibility and generous assurances of correctness. At the same time, their naive implementations are incredible underperformers on today's deeply pipelined processors and horribly latent processor/DRAM subsystems -- making optimal use of (preferably on-die) SRAM cache, minimizing unpredictable branches and eliminating data dependency is of absolutely critical importance, and seperates the men from the boys. Parallelized approaches also deserve more than the scant attention they're here paid. This book ought only get four stars, but there's not yet a superior authority regarding this fascinating, utterly exquisite branch of computer science, a deliciously pure intersection of theory and application. Perhaps I will one day write it [shrug].

Review # 2 was written on 2013-08-27 00:00:00 Sharen Kenton Напокон сам прочитао овог монструма од књиге, требала ми је читава вјечност јер сам прво кренуо са читањем са лаптопа (у питању је електронска верзија са сајта аутора) и тек прије неколико дана ми је дошла на ум генијална идеја да пребацим фајл на Киндл, што је убрзало читање бар десет пута. Пошто ова књига припада области којом се у неку руку бавим, непристојно би било да прескочим писање ривјуа, иако због своје врло уске тематике тешко да ће исти интересовати било кога - ово је књига о базама података, или, прецизније, понајвише о имплементацији подршке за типове података у будућим базама података. Због тога, остатак овог текста (уз, вјерујем, прилично оптимистичну претпоставку да ће након ових уводних редова уопште неко наставити са читањем) састојаће се од мојих покушаја да бар приближно објасним о чему се овде ради, а да малобројне преостале читаоце не увалим у превелику досаду. Прво, неопходан нам је појам релационе базе података. За базу података сматраћемо да је интуитивно позната (мада је покушај потпуно прецизног дефинисања исте већ мало компликованија ствар), а релациона база података била би, вррррррррррррло грубо поједностављено, она у којој су подаци смјештени у табеле. Ако сте некад, а сигурно јесте, видјели нешто попут табеле са студентима у којој имате рецимо број индекса, име, презиме, датум и мјесто рођења и нпр. просјек оцјена и имате неки систем који можете да замолите да вам излиста све студенте из Београда, онда сте се срели са неком имплементацијом поменутом релационог модела (наравно, база података углавном ће садржати више од једне табеле (такође, сасвим десето питање је да ли је поменута имплементација добра или лоша)). Релациони модел и (скоро) све везано за њега има врло прецизне дефиниције укоријењене углавном у теорији скупова и предикатском рачуну првог реда. Поменути модел је модел тзв. друге генерације (моделима прве генерације нећемо се бавити овде, а модели треће генерације још увијек не постоје, што је једна врло повољна околност) и био је доминантан у базноподатном пољу од свог лансирања (почетком седамдесетих) па све до данас, иако се често појављују неки пролазни хитови за које се најављује да ће да га свргну с трона (средином деведесетих то је био објектни модел, а данас имамо извјесне NoSQL моделе, о којима не знам много, али сам прилично скептичан према нечему што се дефинише као негација нечег другог). Даље, неопходно нам је да знамо ко је Крис Дејт (лик који је потписан испод наслова књиге - журим да напоменем, то је фатална грешка на Гудридсу, јер не спомиње другог коаутора, Хјуа Дарвена). Дејт није аутор релационог модела (њега је осмислио Едгар Код), али је дао велики допринос његовом развоју, што кроз прецизирање и систематизовање разноразних појмова, што кроз оригинални допринос у неким пољима. Он је аутор фамозне књиге An Introduction to Database Systems, која представља вјероватно најбољи уџбеник било чега који сам прочитао. Разлог је што Дејт успијева да објасни скоро све појмове везане за (првенствено релационе) базе података врло јасно и сликовито, а да при том не жртвује ни дјелић неопходне прецизности, а поред тога у питању је (што је иначе прилично необично за уџбенике) књига "са ставом" - неки од најзабавнијих дијелова су они у којима Дејт опаучи неког другог аутора због погрешног схватања модела. Ова књига не само да ме је навукла да одаберем управо базе података за оно чиме ћу даље да се бавим, већ је доста утицала и на моје логичко размишљање, невезано за област дјеловања. Скоро смо се приближили поенти данашњег излагања. Наиме, Крис Дејт и Хју Дарвен сматрају да су системи база података будућности управо релациони системи и ништа друго. Упркос популарности објектних система, они им налазе сијасет замјерки и сматрају да све оно што вриједи у објектном моделу већ постоји у (исправно схваћеном) релационом моделу. Међутим, као што ћете видјети ако прочитате било коју Дејтову књигу (или било који његов чланак заправо), они такође сматрају да потпуно "исправна" имплементација релационог модела НЕ ПОСТОЈИ, чак ни у системима који се називају релационим. Због тога дају низ услова које систем треба да задовољи да би се назвао потпуно релационим (по њиховом стандарду) и предлажу своју верзију упитног језика која не пати од аномалија које демонстрира свима нам омиљени SQL. Поменути услови и њихова (екстремно) детаљна објашњења су управо тема ове књиге. Зашто се зове "трећи" манифесто мислим да није толико битно. Сад ћу да дам неколико личних коментара. Прво, ова књига је сува ко барут, што не може да се узме као замјерка, јер једноставно због своје тематике није ни могла да буде другачија. Кад морате да зароните у тако дубоке дубине и да се бавите таквим стварима као што су типови и подтипови, оператори, насљеђивање и остале ствари и да све то потпуно прецизно дефинишете, ту нажалост нема много простора за импровизацију. Поједини дијелови су зато неминовно практично нечитљиви и користе се искључиво као референце (што наводе и сами аутори). Друго, суштину свега овога имате врло лијепо сажету у поменутом Уводу у системе база података, тако да Трећим манифестом треба да се бавите једино ако баш баш БАШ планирате да постанете професионалац у овом пољу. Треће, ипак, књига није сасвим лишена забавних дијелова. Ту првенствено мислим на поглавље о погледима. Шта су погледи? Па, опет врло лабаво, ако имате базу података са некаквим табелама, погледи су табеле дефинисане уз помоћ тих већ постојећих табела које приказују податке на "мало другачији" начин. На примјер, у нашој горе споменутој табели са студентима можете рецимо да дефинишете нову табелу која би садржала све колоне старе табеле осим рецимо датума рођења и онда појединим корисницима дате приступ само тој табели (а не и оригиналној) и на тај начин их спријечите да сазнају датуме рођења студената, иако остале податке могу да виде. Та нова табела вам је тај поглед о коме говоримо (успут, ако ово којим случајем чита неки гњаватор пуриста и ако нађе замјерку овим мојим образложењима намијењеним широј публици, нек скочи у језеро). Погледи су у релационим базама података врло зезнуте ствари (иако се то не би рекло из једноставног примјера који сам дао), нарочито кад је ријеч о њиховом ажурирању (српски: апдејтовању) и Дејт и компанија се са тим малтретирају већ деценијама (до коначног рјешења проблема још није дошло). Забавност поглавља о коме говорим јесте да, за разлику од осталих аспеката модела, Дејт и Дарвен имају потпуно супротна гледишта о погледима (хехе, гледишта о погледима :-) (још би забавније било да сам написао "погледе на погледе")) и оба та гледишта (да не кажем - погледи) су описана у књизи. Прво иде Дејт, па онда Дарвен који критикује Дејта. Главни дио књиге отпада на врло детаљан опис типова података, при чему је фокус највише на односу подтип/надтип и такозваној специјализацији по ограничењу, која је намијењена рјешавању вјековних питања с којима се пате објектни системи, као што је нпр. "Да ли је круг елипса?". У детаље овде нећемо улазити. Према томе, ово је у сваком погледу врло значајно дјело, пошто су базе података, је ли, врло битна област, а овде се са готово патолошком прецизношћу описује како би такав систем требало да изгледа. Иако је књига, као што већ рекох, углавном врло слабо читљива. Примијетићете да до сада апсолутно ни о чему нисам дао своје мишљење (осим о сувоћи књиге). То сам намјерно оставио за крај. Моје субјективно мишљење, засновано на скоро па петнаестогодишњем читању Дејтових списа, јесте да су Дејт и Дарвен УВИЈЕК у праву у својим критикама других аутора. За неке ауторе сам се и лично увјерио (првенствено оне који су писали о релационим базама), а што се тиче објектне технологије, ту нисам стручњак, тако да ми остаје само да вјерујем на ријеч да су концепте о којима говоре (и које критикују) поштено представили - наравно, нема никаквог разлога да им не вјерујем. Такође, аутори су апсолутно успјели да ме увјере да је специјализација по ограничењу једини исправан метод дефинисања подтипова. Дакле, упркос тешкој читљивости, овакав манифест има моју апсолутну подршку и ако неко од критичара има приједлог литературе у којој је описано супротно мишљење, а да је овако темељно и прецизно, то бих волио да прочитам. Још да се вратим на поглавље о погледима. Ко је дакле у праву? Дејт или Дарвен? Иако је питање далеко од ријешеног, ако морам да се опредијелим за побједника, овде је то несумњиво Дарвен, пошто су његове критике Дејтовог модела по мом мишљењу сасвим оправдане. Још једна ситница и завршавам. Поред погледа, друга битна ствар која је предмет спотицања у свијету база података јесу недостајуће информације и такозване НУЛЛ "вриједности". Овде је проблем врло лако илустровати (али врло тешко ријешити) - замислите да у нашој табели са студентима за неког студента не знате датум рођења. Шта ћете уписати у одговарајуће поље? О овоме су написане хиљаде и хиљаде страна и (квалитетно) рјешење се још не назире. Моја замјерка Дејту је да, иако у потпуности подржавам његово демолирање НУЛЛ "вриједности" и свега што из њих слиједи (а слиједи свашта лоше), систем који је он понудио - заснован на тзв. дефаулт вриједностима - такође није довољно добро рјешење из разлога које сад нећу да објашњавам да не бих даље компликовао.