Apostolico–Giancarlo algorithm: Difference between revisions

Revision as of 08:51, 3 December 2016

Latest revision as of 07:58, 11 March 2025

(11 intermediate revisions by 10 users not shown)

Line 1:

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

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

{{No footnotes|date=October 2023}}

In [[computer science]], the '''Apostolico–Giancarlo algorithm''' is a variant of the [[Boyer–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-GiancarloApostolico–Giancarlo speeds this up by recording the number of characters matched at the alignments of <math>{{mvar|T</math>}} in a table, which is combined with data gathered during the pre-processing of <math>{{mvar|P</math>}} 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. [[Digital Object Identifier|doi]]: [https://dx.doi.org/10.1137/0215007 10.1137/0215007].

*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):195-203. [[Digital|pages=195–203 Object Identifier|doi]]: [url=https://dxhal-upec-upem.doiarchives-ouvertes.orgfr/10.1016/S0020hal-0190(97)00107-5 10.101600619574/S0020-0190(97)00107-5]file/ipl2.pdf}}

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

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

* {{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 journal |doi=10., 1995,1002/spe.4380250703 |title=Experimental results on [[String searching algorithm|string matching]] algorithms, |year=1995 |last1=Lecroq |first1=Thierry |journal=[[Software -: Practice &and Experience]] |volume=25( |issue=7):727-765. [[Digital|pages=727–765 Object Identifier|doi]]: [https://dx.doi.org/10.1002/spe.4380250703 10.1002/spe.4380250703].s2cid=15253073}}

{{Strings}}