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 in a text . As with other comparison-based string searches, this is done by aligning to a certain index of and checking whether a match occurs at that index. is then shifted relative to according to the rules of the Boyer–Moore algorithm, and the process repeats until the end of has been reached. Application of the Boyer-Moore shift rules often results in large chunks of the text being skipped entirely.
| Attributes | Values |
|---|
| rdfs:label
| - Apostolico–Giancarlo algorithm (en)
- Algorithme d'Apostolico-Giancarlo (fr)
|
| rdfs:comment
| - 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 in a text . As with other comparison-based string searches, this is done by aligning to a certain index of and checking whether a match occurs at that index. is then shifted relative to according to the rules of the Boyer–Moore algorithm, and the process repeats until the end of has been reached. Application of the Boyer-Moore shift rules often results in large chunks of the text being skipped entirely. (en)
- En informatique, l’algorithme de Apostolico–Giancarlo est une variante de l’algorithme de recherche de chaîne Boyer–Moore dont l'utilisation de base est la recherche d’occurrences d’un motif dans un texte . (fr)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - 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 in a text . As with other comparison-based string searches, this is done by aligning to a certain index of and checking whether a match occurs at that index. is then shifted relative to according to the rules of the Boyer–Moore algorithm, and the process repeats until the end of has been reached. Application of the Boyer-Moore shift rules often results in large chunks of the text being skipped entirely. With regard to the shift operation, Apostolico–Giancarlo is exactly equivalent in functionality to Boyer–Moore. The utility of Apostolico–Giancarlo is to speed up the match-checking operation at any index. With Boyer-Moore, finding an occurrence of in requires that all characters of 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–Moore runs in , where is the length in characters of . Apostolico–Giancarlo speeds this up by recording the number of characters matched at the alignments of in a table, which is combined with data gathered during the pre-processing of 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. (en)
- En informatique, l’algorithme de Apostolico–Giancarlo est une variante de l’algorithme de recherche de chaîne Boyer–Moore dont l'utilisation de base est la recherche d’occurrences d’un motif dans un texte . Comme avec d’autres recherches de chaîne par comparaison, la recherche se fait en alignant à un index particulier de et en vérifiant s’il y a concordance à cet endroit. est ensuite décalé par rapport à en suivant les règles de l’algorithme de Boyer-Moore, et le processus se répète jusqu'à atteindre la fin de . L’application des règles de décalage de Boyer-Moore aboutit souvent à sauter complètement de grandes parties du texte.Concernant l’opération de décalage, Apostolico-Giancarlo est l’exact équivalent fonctionnel de Boyer-Moore. L'utilité de Apostolico-Giancarlo est d'accélérer l’opération de vérification de la concordance à un index donné. Avec Boyer-Moore, trouver une occurrence de dans exige que l’ensemble des caractères de corresponde explicitement. Pour certains motifs et textes, c’est très inefficace. Un exemple simple est celui où le motif et le texte consistent tous deux en un même caractère répété. Dans ce cas, Boyer-Moore s’exécute en , où est la longueur de en caractères. Apostolico-Giancarlo accélère le processus en enregistrant le nombre de caractères qui correspondent aux alignements de dans une table, qui est combinée aux données recueillies lors du pré-traitement de pour éviter les vérifications d’égalité redondantes pour les suites de caractères que l’on sait correspondre. (fr)
|
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)