| dbpprop:abstract
|
- The Rabin-Karp algorithm is a string searching algorithm created by Michael O. Rabin and Richard M. Karp in 1987 that uses hashing to find a substring in a text. It is used for multiple pattern matching rather than single pattern matching. For text of length n and pattern of length m, its average and best case running time is O(n), but the worst case performance of O(nm) is a reason why it is not widely used. However, it has the unique advantage of being able to find any one of k strings or less in O(n) time on average, regardless of the magnitude of k. A practical application of Rabin-Karp is detecting plagiarism. Given source material, Rabin-Karp can rapidly search through a paper for instances of sentences from the source material, ignoring details such as case and punctuation. Because of the abundance of the sought strings, single-string searching algorithms are impractical.
- Der Rabin-Karp-Algorithmus ist ein Suchalgorithmus für Texte, der von Michael O. Rabin und Richard M. Karp entwickelt wurde. Der Algorithmus sucht nach einem Muster, z. B. einer Zeichenkette, innerhalb einer anderen Zeichenkette mit Hilfe von Hash-Werten. In der Einzelmustererkennung ist der Algorithmus nicht weit verbreitet, allerdings ist er von beachtlicher theoretischer Bedeutung und sehr effektiv, um ein Muster mehrfach in einem Text zu suchen. Für einen Text der Länge n und ein Muster der Länge m ist seine durchschnittliche und beste Laufzeit O(n), die (sehr untypische) Laufzeit im schlechtesten Fall beträgt allerdings O(nm). Dies ist einer der Gründe, weshalb der Algorithmus nicht oft benutzt wird. Trotzdem hat er den einzigartigen Vorteil, beliebig viele Zeichenketten in einem Durchlauf im Durchschnitt in O(n) oder weniger zu finden. Eine der einfachsten praktischen Anwendungen von Rabin-Karp ist die Erkennung von Plagiaten: Nehmen wir als Beispiel einen Studenten, der ein Referat über Moby Dick schreibt. Ein Professor könnte aus verschiedenen Quellen zum Thema Moby Dick automatisiert eine Liste aller Sätze erstellen. Rabin-Karp könnte nun schnell das abgegebene Schriftstück durchsuchen und jedes Vorkommen eines der Sätze des Quellmaterials finden. Um das einfache Ausbremsen des Systems mit kleinen Änderungen an den Originalquellen zu vermeiden, können Details, wie z. B. die Zeichensetzung, vorher entfernt und damit ignoriert werden. Aufgrund der Anzahl der gesuchten Zeichenketten wären in diesem Fall Einzel-Zeichenketten-Such-Algorithmen unpraktisch.
- L'algorithme de Rabin-Karp est un algorithme de recherche de chaînes de caractères crée par Michael O. Rabin et Richard M. Karp. Cette méthode recherche un motif donné (ie. une sous-chaîne) dans un texte grâce à du hachage. L'algorithme n'est pas beaucoup employé pour les recherches d'une seule chaîne mais a une importance théorique et s'avère très efficace pour des recherches de sous-chaînes multiples. Pour un texte d'une longueur de n caractères, et une sous-chaîne d'une longueur m, sa complexité moyenne est de O(n). Sa complexité dans le pire des cas est de O(nm) ce qui explique son utilisation relativement limitée. Toutefois, 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), indépendamment de la taille de k.
- ラビン-カープ文字列検索アルゴリズム（Rabin-Karp String Search Algorithm）は、マイケル・ラビンとリチャード・カープが開発した、ハッシュ関数を利用してテキストからパターン（サブ文字列）を探す文字列検索アルゴリズムの一種。1つのパターンの検索にはあまり用いられないが、理論的には重要であり、複数パターンの検索には効果的である。テキストの文字数が n、パターンの文字数が m とした場合、平均および最良の実行時間はO(n)だが、ごく稀に最悪性能として O(nm)となる（広く用いられないのはそのため）。しかし、k個の文字列のいずれかにマッチする部分を検索するのに要する時間は k によらず平均で O(n) となるという独特の利点を持つ。以下、単にラビン-カープまたはラビン-カープ法と略記することがある。 ラビン-カープの単純な応用例として、盗作の検出がある。例えば、学生が『白鯨』に関する英語の論文を書いたとしよう。賢い教授は『白鯨』に関する様々な資料を集め、それらの全文を自動的に抽出するものとする。そこで、ラビン-カープを使えば学生の論文の任意の文がそれら資料からの丸写しかどうかを判定できる。微妙な修正で盗作を判定できなくなるのを防ぐには、大文字・小文字の別を無視し、句読点を無視すればよい。この場合の検索文字列数 k は膨大なので、単一文字列検索アルゴリズムは非現実的である。
- Algorytm Karpa-Rabina jest algorytmem dopasowania wzorca - służy do lokalizowania w tekście określonego podciągu. Dany jest wzorzec <math>x[1\ldots m]</math> (złożony z <math>m</math> znaków) oraz przeszukiwany ciąg <math>y[1\ldots n]</math> (złożony z <math>n</math> znaków; <math>n > m</math>). Problem dopasowania wzorca polega na znalezieniu takiego indeksu <math>i</math>, dla którego <math>y[i\ldots i+m-1] = x[1\ldots m]</math>. W algorytmie Karpa-Rabina wykorzystuje się funkcję mieszającą <math>h</math>. Przeglądane są wszystkie podciągi <math>y_i := y[i\ldots i+m-1]</math> dla <math>i \in [1\ldots n-m]</math>, ale bezpośrednie porównania podciągu <math>y_i</math> z <math>x</math> (które jest bardzo kosztowne) ma miejsce tylko wtedy, gdy <math>h(y_i) = h(x)</math>. O efektywności algorytmu decyduje konstrukcja funkcji mieszającej <math>h</math> - powinna istnieć funkcja <math>N</math> która niskim kosztem wyznacza <math>h(y_{i+1)</math> na podstawie znanej już wartości <math>h(y_i)</math>. W praktyce traktuje się tekst, jako liczbę zapisaną w systemie o określonej podstawie (najczęściej biorąc jako wartości cyfr kody ASCII znaków). Oczekiwana złożoność obliczeniowa jest rzędu <math>O(m+n)</math>. Pseudokod (dane <math>x</math>, <math>y</math>, <math>n</math>, <math>m</math>): <math>Sx \larr h(x)</math> <math>Sy \larr h(y)</math> for <math>i \larr 1</math> to <math>n-m</math> do begin if <math>Sx = Sy</math> then begin porównaj ciąg <math>x[1\ldots m]</math> z podciągiem <math>y[i\ldots i+m-1]</math> if wynik porównania prawdziwy then zwróć indeks <math>i</math> end <math>Sy \larr N(Sy, y, y)</math> end
- Algoritmul Rabin-Karp este un algoritm de căutare în şiruri de caractere, creat de Michael Rabin şi Richard Karp şi care foloseşte hashingul pentru a găsi un subşir al şirului de căutat. Pentru un text de lungime n şi un şablon de lungime m, complexitatea în timp cea mai bună şi cea medie este de O(n), dar în cazurile cele mai rele, ea este de O(mn), şi de aceea algoritmul nu este folosit pe scară largă. Totuşi, el prezintă avantajul că are aceeaşi complexitate indiferent de numărul de şabloane căutate. O utilizare practică a acestui algoritm este detecţia plagiatului. Cu ajutorul algoritmului Rabin-Karp se pot căuta rapid mai multe propoziţii din documentul sursă în acelaşi timp în documentul suspect. Din cauza numărului mare de şiruri care se caută, algoritmii de căutare care oferă performanţe la căutarea unui singur şir sunt nepractici.
- Алгоритм Рабина—Карпа — это алгоритм поиска строки, который ищет шаблон, то есть подстроку, в тексте используя хеширование. Он был разработан в 1987 году Майклом Рабином и Ричардом Карпом. Алгоритм редко используется для поиска одиночного шаблона, но имеет значительную теоретическую важность и очень эффективен в поиске совпадений множественных шаблонов. Для текста длины n и шаблона длины m, его среднее время исполнения и лучшее время исполнения это O(n), но в (весьма нежелательном) худшем случае он имеет производительность O(nm), что является одной из причин того, почему он не слишком широко используется. Однако, алгоритм имеет уникальную особенность находить любую из k строк менее, чем за время O(n) в среднем, независимо от размера k. Одно из простейших практических применений алгоритма Рабина—Карпа состоит в определении плагиата. Скажем, например, что студент пишет работу по Моби Дику. Коварный профессор находит различные исходные материалы по Моби Дику и автоматически извлекает список предложений в этих материалах. Затем, алгоритм Рабина—Карпа может быстро найти в проверяемой статье примеры вхождения некоторых предложений из исходных материалов. Для устранения чувствительности алгоритма к небольшим различиям, можно игнорировать детали, такие как регистр или пунктуация при помощи их удаления. Поскольку количество строк, которые мы ищем, k, очень большое, обычные алгоритмы поиска одиночных строк становятся неэффективными.
- Rabin-Karps algoritm är en algoritm för textsökning där man önskar finna samtliga förekomster av en söksträng i en text. Algoritmen presenterades 1981 av Michael O. Rabin och Richard M. Karp.
- Алгоритм Рабіна-Карпа — алгоритм пошуку рядка запропонований Рабіном і Карпом. Алгоритм показує високу продуктивність на практиці, а також дозволяє узагальнення на інші споріднені задачі. Ідея алгоритму полягає в заміні текстових рядків числами, порівняння яких можна виконувати значно швидше.
|
| rdfs:comment
|
- The Rabin-Karp algorithm is a string searching algorithm created by Michael O. Rabin and Richard M. Karp in 1987 that uses hashing to find a substring in a text. It is used for multiple pattern matching rather than single pattern matching. For text of length n and pattern of length m, its average and best case running time is O(n), but the worst case performance of O(nm) is a reason why it is not widely used.
- Der Rabin-Karp-Algorithmus ist ein Suchalgorithmus für Texte, der von Michael O. Rabin und Richard M. Karp entwickelt wurde. Der Algorithmus sucht nach einem Muster, z. B. einer Zeichenkette, innerhalb einer anderen Zeichenkette mit Hilfe von Hash-Werten. In der Einzelmustererkennung ist der Algorithmus nicht weit verbreitet, allerdings ist er von beachtlicher theoretischer Bedeutung und sehr effektiv, um ein Muster mehrfach in einem Text zu suchen.
- L'algorithme de Rabin-Karp est un algorithme de recherche de chaînes de caractères crée par Michael O. Rabin et Richard M. Karp. Cette méthode recherche un motif donné (ie. une sous-chaîne) dans un texte grâce à du hachage. L'algorithme n'est pas beaucoup employé pour les recherches d'une seule chaîne mais a une importance théorique et s'avère très efficace pour des recherches de sous-chaînes multiples.
- Algorytm Karpa-Rabina jest algorytmem dopasowania wzorca - służy do lokalizowania w tekście określonego podciągu. Dany jest wzorzec <math>x[1\ldots m]</math> (złożony z <math>m</math> znaków) oraz przeszukiwany ciąg <math>y[1\ldots n]</math> (złożony z <math>n</math> znaków; <math>n > m</math>).
- Algoritmul Rabin-Karp este un algoritm de căutare în şiruri de caractere, creat de Michael Rabin şi Richard Karp şi care foloseşte hashingul pentru a găsi un subşir al şirului de căutat. Pentru un text de lungime n şi un şablon de lungime m, complexitatea în timp cea mai bună şi cea medie este de O(n), dar în cazurile cele mai rele, ea este de O(mn), şi de aceea algoritmul nu este folosit pe scară largă.
- Алгоритм Рабина—Карпа — это алгоритм поиска строки, который ищет шаблон, то есть подстроку, в тексте используя хеширование. Он был разработан в 1987 году Майклом Рабином и Ричардом Карпом.
- Rabin-Karps algoritm är en algoritm för textsökning där man önskar finna samtliga förekomster av en söksträng i en text. Algoritmen presenterades 1981 av Michael O. Rabin och Richard M. Karp.
- Алгоритм Рабіна-Карпа — алгоритм пошуку рядка запропонований Рабіном і Карпом. Алгоритм показує високу продуктивність на практиці, а також дозволяє узагальнення на інші споріднені задачі.
|
![[RDF Data]](/statics/sw-cube.png)
