从DNA到Twitter：解析概率模式匹配理论与应用

需积分: 0 151 浏览量更新于2024-07-19 1 收藏 11.56MB PDF 举报

"《分析模式匹配：从DNA到Twitter》是一本深入研究信息技术领域中的关键概念的专著，由Philippe Jacquet撰写，共352页，并附有高清带详细目录的PDF格式，适用于研究人员和研究生。该书的焦点在于探讨概率性模式匹配方法，这是一种通过分析组合学和分析信息论来预测模式匹配算法性能的精确技术。在分子生物学、电信通信乃至社交媒体内容分类等多个领域，作者展示了如何运用这些技术来解决实际问题，如通过DNA序列鉴别猫和狗的区别，或者验证莎士比亚作品的真实性。书中分为两部分：第一部分汇总了可以通过分析方法获取的模式匹配问题的结果，包括对数字树、后缀树、字符串复杂性和基于字符串的数据压缩等各种数据结构的应用。第二部分则聚焦于实践应用，不仅依赖于第一部分的结果，还引入了新的方法论，如梅林变换和分析泊松化等高级工具。这些新方法进一步增强了理论与实际操作之间的联系。全书超过100个章节末尾的问题设计，旨在帮助读者将学到的理论知识转化为实际操作技能，从DNA序列的分析到处理Twitter内容的复杂性。《分析模式匹配：从DNA到Twitter》是一本极具深度和实用性的书籍，不仅涵盖了基础的模式匹配理论，还展示了其在现代科技领域的广泛应用，对于想要在这个领域深入研究或从事数据分析工作的专业人士来说，无疑是一本不可或缺的参考资料。"

highlyinterestingandunusual.
InChapter8 we continue analyzing digitaltreesbut now those built fromcorrelated
strings.Namelywestudysuffixtrees,whicharetriesconstructedfromthesuffixesofa
string.Inparticularwefocusoncharacterizingmathematicallythelengthofthelongest
substringofthetextoccurringatagivenpositionthathasanothercopyinthetext.This
length,whenaveragedoverallpossiblepositionsofthetext,isactuallythetypicaldepth
in a suffix trie built over (randomly generated) text. We analyze it using analytic
techniquessuchasgeneratingfunctionsandtheMellintransform.Moreimportantly,we
reduceitsanalysistotheexactpatternmatchingdiscussedindepthinChapter2.Infact,
we prove that the probability generating function of the depth in a suffix trie is
asymptoticallyclose to the probability generating functionof the depth in a triethatis
builtovernindependentlygeneratedtextsanalyzedinChapter7,sowehaveaprettygood
understandingofitsprobabilisticbehavior.Thisallowsustoconcludethatthedepthina
suffix trie is asymptotically normal. Finally, we turn our attention to an application of
suffixtreestotheanalysisoftheLempel–Ziv’77scheme.Weaskthequestionhowmany
LZ’77 phrases there are in a randomly generated string. This number is known as the
multiplicityparameterandweestablishitsasymptoticdistribution.
In Chapter 9 we study a data structure that is the most popular and the hardest to
analyze,namelytheLempel–Ziv’78scheme.Ourgoalistocharacterizeprobabilistically
thenumberofLZ’78phrasesanditsredundancy.Boththesetasksdrewalotofattention
asbeingopenanddifficultuntilAldousandShields(1988)andJacquetandSzpankowski
(1995) solved them for memoryless sources. We present here a simplified proof for
extendedresults:thecentrallimittheoremforthenumberofphrasesandtheredundancy
aswellasthemoderateandlargedeviationfindings.Westudythisproblembyreducingit
toananalysisoftheassociateddigitalsearchtree,alreadydiscussedinPartinChapter7.
Inparticular,weestablishthecentrallimittheoremandlargedeviationsforthetotalpath
lengthinthedigitalsearchtree.
Finally, in Chapter 10 we study the string complexity and also the joint string
complexity,whichisdefinedasthecardinalityofdistinctsubwordsofastringorstrings.
Thestringcomplexitycapturesthe“richnessofthelanguage”usedinasequence,andit
hasbeenstudiedquiteextensivelyfromtheworstcasepointofview.Ithasalsoturnedout
thatthejointstringcomplexitycanbeusedquitesuccessfullyfortwitterclassification
(seeJacquet,Milioris,andSzpankowski(2013)).Inthischapterwefocusonanaverage
caseanalysis.Thejointstringcomplexityisparticularlyinterestingandchallengingfrom
the analysispoint of view. It requires novel analytic tools such as the two-dimensional
Mellintransform,depoissonization,andthesaddlepointmethod.
Nearlyeverychapterisaccompaniedbyasetofproblemsandrelatedbibliography.In
the problemsectionswe ask the reader to complete a sketchy proof, to solve a similar
problem, or to actually work on an open problem. In the bibliographical sections we
brieflydescribesomerelatedliterature.
Finally, to ease the reading of this book, we illustrate each chapter with an original
comicsketch.Eachsketchissomewhatrelatedtothetopicofthecorrespondingchapter,
asdiscussedbelow.

Acknowledgments

This book is dedicated to Philippe Flajolet, the father of analytic combinatorics, our

friend andmentorwho passed away suddenly on March 22, 2011.An obituary – from

which we freely borrow here – was recently published by Salvy, Sedgewick, Soria,

Szpankowski,andVallee(2011).

WebelievethatthisbookwaspossiblethankstothetirelesseffortsofPhilippeFlajolet,

hisextensiveandfar-reachingbodyofwork,andhisscientificapproachtothestudyof

algorithms, including the development of the requisite mathematical and computational

tools.Philippeisbestknownforhisfundamentaladvancesinmathematicalmethodsfor

the analysis of algorithms; his research also opened new avenues in various areas of

applied computer science, including streaming algorithms, communication protocols,

databaseaccessmethods,datamining,symbolicmanipulation,text-processingalgorithms,

and random generation. He exulted in sharing his passion: his papers had more than a

hundreddifferentco-authors(includingthepresentauthors)andhewasaregularpresence

atscientificmeetingsallovertheworld.

PhilippeFlajolet’sresearchlaidthefoundationofasubfieldofmathematicsnowknown

as analytic combinatorics. His lifework Analytic Combinatorics (Cambridge University

Press, 2009, co-authored with R. Sedgewick) is a prodigious achievement, which now

defines the field and is already recognized as an authoritative reference. Analytic

combinatorics is a modern basis for the quantitative study of combinatorial structures

(suchaswords,trees,mappings,andgraphs),withapplicationstoprobabilisticstudyof

algorithmsbasedonthesestructures.Italsostronglyinfluencesotherscientificareas,such

asstatisticalphysics,computationalbiology,andinformationtheory.Withdeephistoric

rootsinclassicalanalysis,thebasisofthefieldliesintheworkofKnuth,whoputthe

studyofalgorithmsontoafirmscientificbasis,startinginthelate1960swithhisclassic

series of books. Philippe Flajolet’s work took the field forward by introducing original

approachesintocombinatoricsbasedontwotypesofmethods:symbolicandanalytic.The

symbolic side is based on the automation of decision procedures in combinatorial

enumerationtoderivecharacterizationsofgeneratingfunctions.Theanalytic sidetreats

those generating functions as functions in the complex plane and leads to a precise

characterizationoflimitdistributions.

Finally, Philippe Flajolet was the leading figure in the development of a large

internationalcommunity(whichagainincludesthepresentauthors)devotedtoresearchon

probabilistic, combinatorial, and asymptotic methods in the analysis of algorithms. His

legacyisalivethroughthiscommunity.Wearestilltryingtocopewiththelossofour

friendandmentor.

Whileputtingthefinaltouchestothisbook,thetragicshootingoccurredinParisofthe

famous French cartoonists at Charlie Hebdo. We are sure that this event would shock

Philippe Flajolet, who had an inimitable sense of humour. He mocked himself and his

friends.Wewereoftenonthereceivingendofhishumour.Wetookit,asmostdid,asa

proofofaffection.Cartoonistsand scientistshavesomething incommon: offendingthe

apparenttruthisanecessarysteptowardbetterknowledge.

Thereisalonglistofothercolleaguesandfriendsfromwhomwebenefitedthrough

their encouragement and constructive comments. They have helped us in various ways

duringourworkontheanalysisofalgorithmsandinformationtheory.Wementionhere

onlyafew:AlbertoApostolico,YongwookChoi,LucDevroye,MichaelDrmota,Ananth

Grama,H-K.Hwang,SvanteJanson,JohnKieffer,ChuckKnessl,YiannisKontoyiannis,

MehmetKoyuturk,GuyLouchard,StefanoLonardi,PierreNicodeme,RalphNeininger,

GahyuanPark,MireilleRégnier,YuriyReznik,BobSedgewick,GadielSeroussi,Brigitte

Vallée, Sergio Verdu, Mark Ward, Marcelo Weinberger. We thank Bob Sedgewick for

writingtheforeword.

Finally,nobigprojectlikethiscanbecompletedwithouthelpfromourfamilies.We

thankVéronique,Manou,Lili,Mariola,LukaszandPaulinafromthebottomofourhearts.

This book has been written over the last five years, while we have been traveling

around the world carrying (electronically) numerous copies of various drafts. We have

receivedinvaluablehelpfromthestaffandfacultyofINRIA,FranceandtheDepartment

ofComputerSciencesatPurdueUniversity.ThesecondauthorisgratefultotheNational

ScienceFoundation,whichhassupportedhisworkoverthelast30years.Wehavealso

received support from institutions around the world that have hosted us and our book:

INRIA, Rocquencourt; Alcatel-Lucent, Paris; LINCS, Paris; the Gdańsk University of

Technology, Gdańsk; the University of Hawaii; and ETH, Zurich. We thank them very

much.

PHILIPPEJACQUET

WOJTEKSZPANKOWSKI

Aboutthesketches

In order to ease the reading of thisbook,fullof dry equations, Philippe drew a comic

sketchforeachchapter.Inthesesketchesweintroducedtworecurrentcomiccharacters.

They are undefined animals like rats, worms, or lizards, sometimes more like fish or

butterflies.We,WojtekandPhilippe,appearin somesketches: Wojtekwithhis famous

moustacheappearsasthebutterflyhunterandPhilippeappearsasafisherman.

Foruspatternsarelikesmallanimalsrunningoveratext,andweseeatextlikeaforest

oragardenfullofwords,asillustratedbelow.Wehavegivennamestothesetwoanimals:

PatforPatriciaTern,andMatforMathewTching.TheyaremostlyinspiredbyPhilippe’s

twincats,CalysandGypsiewhooftenplayandhidewherevertheycan.

Letusgiveyousomehintsonhowtoreadthesesketches:

1. The probabilistic model chapter shows Pat and Mat in a chess game, because

probabilityandgamesaredeeplyentangledconcepts.Hereisthequestion:whowill

winthegame(chessmat)andwhowilllose(pat)?Coloursinthecheckerboardare

omittedinordertocomplicatethepuzzle.

2. Inexactstringmatching,PatandMatareintheirmostdramaticsituation:escaping

thepatternmatchinghunters.

3. In the constrained pattern matching chapter, Pat and Mat must escape a stubborn

pattern matching hunter who is ready to chase them in the hostile (constrained)

submarinecontext.

4. In general string matching, the issue is how to catch a group of patterns. This is

symbolisedbyafishermanholdingseveralhooks.Whetherthefishermanlookslike

Philippeisstillanopenquestion,buthetriedhisbest.

5. In the subsequence pattern matching chapter, Pat and Mat are butterflies facing a

terrible hunter. Yes, he looks like Wojtek, but without his glasses, so that the

butterflieshaveachance.

6. Inthealgorithmsanddatastructureschapter,PatandMatarerestingunderthemost

famouspatternmatchingdatastructure:thetree.Inthiscase,thetreeisanappletree,

剩余351页未读，继续阅读

ignite678@126.com

粉丝: 2
资源: 42

从DNA到Twitter：解析概率模式匹配理论与应用

「漏洞分析」Analytic_Tradecraft_in_the_Real_World - 安全资讯.zip

An_Analytic_Data_Engine_for_Visualization_in_Tableau_1.pdf

这个sql语句哪里错 insert into analytic_double_count (`1_pro_cot`) VALUES null

给一个在Oracle数据库中使用ANALYTIC VIEW语法的例子

在mysql analytic_double表中，增加字段名称为 从1_probability 到44_probability的字段 应该怎么写

在mysql analytic_double表中，增加字段名称为 从1_probability 到44_probability的类型为 varchar(255) COLLATE utf8_bin DEFAULT NULL字段 语句应该怎么写

在mysql analytic_double表中，利用循环的方式，增加字段名称为 从1_probability 到44_probability的类型为 varchar(255) COLLATE utf8_bin DEFAULT NULL字段 语句应该怎么写

已知连续时间的微分方程matlab

python期权定价蒙特卡洛

最新资源

在mysql analytic_double表中，增加字段名称为从1_probability 到44_probability的字段应该怎么写

在mysql analytic_double表中，增加字段名称为从1_probability 到44_probability的类型为 varchar(255) COLLATE utf8_bin DEFAULT NULL字段语句应该怎么写

在mysql analytic_double表中，利用循环的方式，增加字段名称为从1_probability 到44_probability的类型为 varchar(255) COLLATE utf8_bin DEFAULT NULL字段语句应该怎么写