Apostolico–Giancarlo algorithm: Difference between revisions

Revision as of 17:45, 2 April 2012

Latest revision as of 07:58, 11 March 2025

(20 intermediate revisions by 18 users not shown)

Line 1:

{{Short description|Optimization of Boyer–Moore string-search algorithm}}

{{context|date=December 2011}}

{{LeadNo rewritefootnotes|date=SeptemberOctober 20092023}}

In [[computer science]], the '''Apostolico–Giancarlo algorithm''' is a variant of the [[Boyer-MooreBoyer–Moore string -search algorithm]], the basic application of which is searching for occurrences of a pattern <math>{{mvar|P</math>}} in a text <math>{{mvar|T</math>}}. As with other comparison-based string searches, this is done by aligning <math>{{mvar|P</math>}} to a certain index of <math>{{mvar|T</math>}} and checking whether a match occurs at that index. <math>{{mvar|P</math>}} is then shifted relative to <math>{{mvar|T</math>}} according to the rules of the Boyer-MooreBoyer–Moore algorithm, and the process repeats until the end of <math>{{mvar|T</math>}} has been reached. Application of the Boyer-MooreBoyer–Moore shift rules often results in large chunks of the text being skipped entirely.

With regard to the shift operation, Apostolico-GiancarloApostolico–Giancarlo is exactly equivalent in functionality to Boyer-MooreBoyer–Moore. The utility of Apostolico-GiancarloApostolico–Giancarlo is to speed up the match-checking operation at any index. With Boyer-MooreBoyer–Moore, finding an occurrence of <math>{{mvar|P</math>}} in <math>{{mvar|T</math>}} requires that all <math>{{mvar|n</math>}} characters of <math>{{mvar|P</math>}} be explicitly matched. For certain patterns and texts, this is very inefficient -– a simple example is when both pattern and text consist of the same repeated character, in which case Boyer-MooreBoyer–Moore runs in <{{math>|O(n m''nm'')</math>}}, where <math>{{mvar|m</math>}} is the length in characters of <math>{{mvar|T</math>}}. Apostolico–Giancarlo speeds this up by recording the number of characters matched at the alignments of {{mvar|T}} in a table, which is combined with data gathered during the pre-processing of {{mvar|P}} to avoid redundant equality checking for sequences of characters that are known to match. It can be seen as a generalization of the [[Galil rule]].

==References==

* {{cite journal |doi=10.1137/0215007 |title=The Boyer–Moore–Galil String Searching Strategies Revisited |year=1986 |last1=Apostolico |first1=Alberto |last2=Giancarlo |first2=Raffaele |journal=[[SIAM Journal on Computing]] |volume=15 |pages=98–105 |url=https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1456&context=cstech}}

*APOSTOLICO A., GIANCARLO R., 1986, The Boyer-Moore-Galil string searching strategies revisited, [[SIAM Journal on Computing]] 15(1):98-105.

*CROCHEMORE, M.,{{cite LECROQ,journal T|doi=10., 1997,1016/S0020-0190(97)00107-5 |title=Tight bounds on the complexity of the Apostolico–GiancarloApostolico-Giancarlo algorithm, |year=1997 |last1=Crochemore |first1=Maxime |last2=Lecroq |first2=Thierry |journal=[[Information Processing Letters]] |volume=63( |issue=4) |pages=195–203 |url=https:195//hal-upec-upem.archives-ouvertes.fr/hal-20300619574/file/ipl2.pdf}}

*CROCHEMORE, {{cite book |last=Crochemore |first1=M., RYTTER,|last2=Rytter |first2=W., |author2-link=Wojciech Rytter |year=1994, |title=Text Algorithms, |publisher=[[Oxford University Press]].}}

*GUSFIELD, {{cite book |last=Gusfield |first=D., |year=1997, |title=Algorithms on stringsStrings, treesTrees, and sequencesSequences: [[Computer science|Computer Science]] and Computational Biology, |publisher=[[Cambridge University Press]]. |isbn=0-521-58519-8}}

*LECROQ, {{cite thesis |last=Lecroq |first=T., |year=1992, |title=Recherches de mot,Mots |type=Ph. D. Thesis, |publisher=[[Orléans|University of Orléans]], France.}}

*LECROQ, T.,{{cite 1995,journal |doi=10.1002/spe.4380250703 |title=Experimental results on [[String searching algorithm|string matching]] algorithms, Software|year=1995 -|last1=Lecroq |first1=Thierry |journal=[[Software: Practice &and Experience]] |volume=25( |issue=7):727-765. |pages=727–765 |s2cid=15253073}}

{{Strings}}

{{DEFAULTSORT:Apostolico–Giancarlo Algorithm}}

{{DEFAULTSORT:Apostolico–GiancarloApostolico-Giancarlo Algorithm}}

[[Category:String matching algorithms]]