| Property |
Value |
| dbo:abstract
|
- L’algorithme de Rabin-Karp ou Karp-Rabin est un algorithme de recherche de sous-chaîne créé par Richard M. Karp et Michael O. Rabin (1987). Cette méthode recherche un ensemble de motifs donnés (c’est-à-dire des sous-chaînes) dans un texte grâce à une fonction de hachage. L’algorithme n’est pas beaucoup employé pour les recherches d’une unique sous-chaîne mais a une importance théorique et s’avère très efficace pour des recherches de multiples sous-chaînes. Pour un texte d’une longueur de n caractères, et p sous-chaînes d’une longueur totale de m, sa complexité moyenne est en O(n+m) pour une utilisation mémoire en O(p). Mais, dans le pire des cas, sa complexité est de O(nm), ce qui explique son utilisation relativement limitée. En comparaison, l’algorithme de recherche de chaînes d’Aho-Corasick a une complexité asymptotique, dans le pire des cas, en O(n+m) pour une utilisation mémoire en O(m). Il a l’avantage d’être capable de trouver dans un texte une sous-chaîne présente dans un ensemble de k chaînes, avec une complexité moyenne de O(n+m) indépendamment de la taille de k. Ainsi, son efficacité pour les recherches de multiples sous-chaînes, sans tenir compte de la casse ou de la ponctuation, le rend utile pour la détection de plagiat. (fr)
- L’algorithme de Rabin-Karp ou Karp-Rabin est un algorithme de recherche de sous-chaîne créé par Richard M. Karp et Michael O. Rabin (1987). Cette méthode recherche un ensemble de motifs donnés (c’est-à-dire des sous-chaînes) dans un texte grâce à une fonction de hachage. L’algorithme n’est pas beaucoup employé pour les recherches d’une unique sous-chaîne mais a une importance théorique et s’avère très efficace pour des recherches de multiples sous-chaînes. Pour un texte d’une longueur de n caractères, et p sous-chaînes d’une longueur totale de m, sa complexité moyenne est en O(n+m) pour une utilisation mémoire en O(p). Mais, dans le pire des cas, sa complexité est de O(nm), ce qui explique son utilisation relativement limitée. En comparaison, l’algorithme de recherche de chaînes d’Aho-Corasick a une complexité asymptotique, dans le pire des cas, en O(n+m) pour une utilisation mémoire en O(m). Il a l’avantage d’être capable de trouver dans un texte une sous-chaîne présente dans un ensemble de k chaînes, avec une complexité moyenne de O(n+m) indépendamment de la taille de k. Ainsi, son efficacité pour les recherches de multiples sous-chaînes, sans tenir compte de la casse ou de la ponctuation, le rend utile pour la détection de plagiat. (fr)
|
| dbo:discoverer
| |
| dbo:namedAfter
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 13110 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:année
| |
| prop-fr:annéePremièreÉdition
| |
| prop-fr:auteur
| |
| prop-fr:date
|
- mars 1987 (fr)
- mars 1987 (fr)
|
| prop-fr:doi
| |
| prop-fr:fr
|
- Fonction de hachage déroulante (fr)
- Fonction de hachage déroulante (fr)
|
| prop-fr:isbn
| |
| prop-fr:journal
|
- IBM Journal of Research and Development (fr)
- IBM Journal of Research and Development (fr)
|
| prop-fr:langue
| |
| prop-fr:lienAuteur
|
- Michael O. Rabin (fr)
- Richard Karp (fr)
- Thomas H. Cormen (fr)
- Michael O. Rabin (fr)
- Richard Karp (fr)
- Thomas H. Cormen (fr)
|
| prop-fr:lieu
|
- Cambridge, Massachusetts (fr)
- Cambridge, Massachusetts (fr)
|
| prop-fr:nom
|
- Rabin (fr)
- Karp (fr)
- Rabin (fr)
- Karp (fr)
|
| prop-fr:numéro
| |
| prop-fr:numéroD'édition
| |
| prop-fr:pages
| |
| prop-fr:pagesTotales
| |
| prop-fr:passage
| |
| prop-fr:prénom
|
- Richard M. (fr)
- Michael O. (fr)
- Richard M. (fr)
- Michael O. (fr)
|
| prop-fr:texte
|
- fonction de hachage déroulante (fr)
- fonction de hachage déroulante (fr)
|
| prop-fr:titre
| |
| prop-fr:titreChapitre
|
- The Rabin–Karp algorithm (fr)
- The Rabin–Karp algorithm (fr)
|
| prop-fr:trad
|
- Rolling hash (fr)
- Rolling hash (fr)
|
| prop-fr:url
|
- http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.9502&rep=rep1&type=pdf|consulté le=2013-09-24 (fr)
- http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.9502&rep=rep1&type=pdf|consulté le=2013-09-24 (fr)
|
| prop-fr:volume
| |
| prop-fr:wikiPageUsesTemplate
| |
| prop-fr:éditeur
|
- MIT Press (fr)
- MIT Press (fr)
|
| dct:subject
| |
| rdfs:comment
|
- L’algorithme de Rabin-Karp ou Karp-Rabin est un algorithme de recherche de sous-chaîne créé par Richard M. Karp et Michael O. Rabin (1987). Cette méthode recherche un ensemble de motifs donnés (c’est-à-dire des sous-chaînes) dans un texte grâce à une fonction de hachage. L’algorithme n’est pas beaucoup employé pour les recherches d’une unique sous-chaîne mais a une importance théorique et s’avère très efficace pour des recherches de multiples sous-chaînes. (fr)
- L’algorithme de Rabin-Karp ou Karp-Rabin est un algorithme de recherche de sous-chaîne créé par Richard M. Karp et Michael O. Rabin (1987). Cette méthode recherche un ensemble de motifs donnés (c’est-à-dire des sous-chaînes) dans un texte grâce à une fonction de hachage. L’algorithme n’est pas beaucoup employé pour les recherches d’une unique sous-chaîne mais a une importance théorique et s’avère très efficace pour des recherches de multiples sous-chaînes. (fr)
|
| rdfs:label
|
- ラビン-カープ文字列検索アルゴリズム (ja)
- Algorithme de Rabin-Karp (fr)
- Rabin–Karp algorithm (en)
- Алгоритм Рабина — Карпа (ru)
- Алгоритм Рабіна — Карпа (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
