| Property |
Value |
| dbo:abstract
|
- 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)
- 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)
|
| dbo:basedOn
| |
| dbo:namedAfter
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 3419 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:année
|
- 1986 (xsd:integer)
- 1992 (xsd:integer)
- 1994 (xsd:integer)
- 1995 (xsd:integer)
- 1997 (xsd:integer)
|
| prop-fr:auteur
|
- A. Apostolico (fr)
- D. Gusfield (fr)
- M. Crochemore (fr)
- R. Giancarlo (fr)
- T. Lecroq (fr)
- Thierry Lecroq (fr)
- W. Rytter (fr)
- A. Apostolico (fr)
- D. Gusfield (fr)
- M. Crochemore (fr)
- R. Giancarlo (fr)
- T. Lecroq (fr)
- Thierry Lecroq (fr)
- W. Rytter (fr)
|
| prop-fr:doi
|
- 10.100200 (xsd:double)
- 10.101600 (xsd:double)
- 10.113700 (xsd:double)
|
| prop-fr:isbn
| |
| prop-fr:langue
| |
| prop-fr:lieu
|
- France (fr)
- New York (fr)
- Cambridge/New York/Melbourne (fr)
- France (fr)
- New York (fr)
- Cambridge/New York/Melbourne (fr)
|
| prop-fr:lireEnLigne
| |
| prop-fr:natureOuvrage
|
- thèse de doctorat en informatique (fr)
- thèse de doctorat en informatique (fr)
|
| prop-fr:numéro
|
- 1 (xsd:integer)
- 4 (xsd:integer)
- 7 (xsd:integer)
|
| prop-fr:pagesTotales
|
- 412 (xsd:integer)
- 534 (xsd:integer)
|
| prop-fr:passage
|
- 98 (xsd:integer)
- 195 (xsd:integer)
- 727 (xsd:integer)
|
| prop-fr:présentationEnLigne
| |
| prop-fr:périodique
| |
| prop-fr:sousTitre
|
- Computer Science and Computational Biology (fr)
- Computer Science and Computational Biology (fr)
|
| prop-fr:titre
|
- Tight bounds on the complexity of the Apostolico-Giancarlo algorithm (fr)
- Algorithms on Strings, Trees, and Sequences (fr)
- Experimental results on string matching algorithms (fr)
- Recherches de mot (fr)
- Text Algorithms (fr)
- The Boyer–Moore–Galil String Searching Strategies Revisited (fr)
- Tight bounds on the complexity of the Apostolico-Giancarlo algorithm (fr)
- Algorithms on Strings, Trees, and Sequences (fr)
- Experimental results on string matching algorithms (fr)
- Recherches de mot (fr)
- Text Algorithms (fr)
- The Boyer–Moore–Galil String Searching Strategies Revisited (fr)
|
| prop-fr:volume
|
- 15 (xsd:integer)
- 25 (xsd:integer)
- 63 (xsd:integer)
|
| prop-fr:wikiPageUsesTemplate
| |
| prop-fr:éditeur
| |
| dct:subject
| |
| rdfs:comment
|
- 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)
- 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)
|
| rdfs:label
|
- Algorithme d'Apostolico-Giancarlo (fr)
- Apostolico–Giancarlo algorithm (en)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
