| rdfs:comment
| - Rabin–Karpův algoritmus je v informatice jedním z algoritmů pro vyhledávání textu. Vytvořili ho Michael O. Rabin a Richard M. Karp v roce 1987. Algoritmus hledá řadu vzorků najednou a používá k tomu hašovací funkci. Pro text délky n a p vzorků společné délky m je jeho průměrná a nejlepší složitost O(n+m) v prostoru O(p) a jeho nejhorší složitost je O(nm). Praktické využití Rabinova-Karpova algoritmu je odhalování plagiátorství. Vzhledem k množství hledaných řetězců jsou algoritmy, které vyhledávají jeden řetězec, nepraktické. (cs)
- 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. (sv)
- 在计算机科学中，拉宾-卡普算法（英語：Rabin–Karp algorithm）或卡普-拉宾算法（Karp–Rabin algorithm），是一种由理查德·卡普与迈克尔·拉宾于1987年提出的、使用散列函数以在文本中搜寻单个模式串的字符串搜索算法单次匹配。该算法先使用旋转哈希以快速筛出无法与给定串匹配的文本位置，此后对剩余位置能否成功匹配进行检验。此算法可推广到用于在文本搜寻单个模式串的所有匹配或在文本中搜寻多个模式串的匹配。 若要在一段文本中找出单个模式串的一个匹配，此算法具有线性时间的平均复杂度，其运行时间与待匹配文本和模式串的长度成线性关系。虽然平均情况下，此算法表现优异，但下，其复杂度为文本长与模式串长的乘积。当在文本中搜寻多个匹配时，其具有线性时间的平均复杂度（与文本串长、模式串长、模式串所有匹配总长三者的和成线性关系）。相对地，另一种用于找出模式串所有匹配的AC自动机算法的最坏情况复杂度与文本串长、模式串长、模式串所有匹配总数（而非总长）成正比。 此算法的一个实际应用为（如论文查重）。在给定原材料与待查重论文的情况下，此算法可以迅速在论文中搜寻原材料中的句子，同时忽略诸如大小写与标点等细节。由于原材料中的字符串过多，故单字符串搜索算法在此处不适用。 (zh)
- Алгоритм Рабіна-Карпа — алгоритм пошуку рядка запропонований Рабіном і Карпом. Алгоритм показує високу продуктивність на практиці, а також дозволяє узагальнення на інші споріднені задачі. Ідея алгоритму полягає в заміні текстових рядків числами, порівняння яких можна виконувати значно швидше. (uk)
- في عام 1987 قام الباحثان ريتشارد م. كارب ومايكل أ. رابين بإنشاء خوارزمية بحث في النصوص سُميت باسم خوارزمية رابين – كارب أو خوارزمية كارب – رابين. وهي تُعد من الخوارزميات المشهورة في علم الحاسوب. تستخدم هذه الخوارزمية مبدءًا من مبادئ التجزئة (hashing) لإيجاد تطابق تام لسلسلة من الرموز (string) في نص وهو التجزئة المتدرجة (rolling hash). باستخدام التجزئة المتدرجة تقوم الخوارزمية بشكل سريع باستثناء مواقع من النص لا يُمكن مطابقتها للسلسلة المراد البحث عنها، وتكتفي بالبحث ضمن المواقع المتبقية عن التطابق المطلوب. من الممكن تعميم فكرة الخوارزمية للبحث عن أكثر من تطابق واحد للسلسلة في نفس النص، أو البحث عن تطابق لعدة سلاسل مختلفة فيه. (ar)
- Es un Algoritmo de búsqueda de subcadenas simple enunciado por Michael Oser Rabin y Richard Manning Karp en 1987. Este algoritmo se basa en tratar cada uno de los grupos de m caracteres del texto (siendo m el número de símbolos del patrón) del texto como un índice de una tabla de valores hash (la llamaremos tabla de dispersión), de manera que si la función hash de los m caracteres del texto coincide con la del patrón es posible que hayamos encontrado un acierto. para verificarlo hay que comparar el texto con el patrón, ya que la función hash elegida puede presentar colisiones. (es)
- 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 (Worst-Case-Laufzeit) 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 Zeich (de)
- In computer science, the Rabin–Karp algorithm or Karp–Rabin algorithm is a string-searching algorithm created by Richard M. Karp and Michael O. Rabin that uses hashing to find an exact match of a pattern string in a text. It uses a rolling hash to quickly filter out positions of the text that cannot match the pattern, and then checks for a match at the remaining positions. Generalizations of the same idea can be used to find more than one match of a single pattern, or to find matches for more than one pattern. (en)
- 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'algoritmo di Rabin–Karp è un algoritmo di pattern matching su stringhe proposto da Michael O. Rabin e Richard M. Karp nel 1987. Utilizza una funzione di hash per individuare possibili occorrenze del pattern, e per la ricerca di un pattern di lunghezza in un testo di lunghezza ha una complessità computazionale al caso medio di in tempo e di in spazio, e di in tempo al caso pessimo. (it)
- ラビン-カープ文字列検索アルゴリズム（英: Rabin-Karp string search algorithm）は、マイケル・ラビンとリチャード・カープが開発した、ハッシュ関数を利用してテキストからパターン（サブ文字列）を探す文字列検索アルゴリズムの一種。1つのパターンの検索にはあまり用いられないが、理論的には重要であり、複数パターンの検索には効果的である。テキストの文字数が n、パターンの文字数が m とした場合、平均および最良の実行時間はO(n)だが、ごくまれに最悪性能として O(nm)となる（広く用いられないのはそのため）。しかし、k個の文字列のいずれかにマッチする部分を検索するのに要する時間は k によらず平均で O(n) となるという独特の利点を持つ。以下、単にラビン-カープまたはラビン-カープ法と略記することがある。 (ja)
- Algorytm Karpa-Rabina jest algorytmem dopasowania wzorca – służy do lokalizowania w tekście określonego podciągu. Został stworzony w 1987 roku przez Michaela O. Rabina i Richarda Karpa. Dany jest wzorzec (złożony z znaków) oraz przeszukiwany ciąg (złożony z znaków; ). Problem dopasowania wzorca polega na znalezieniu takiego indeksu dla którego W algorytmie Karpa-Rabina wykorzystuje się funkcję mieszającą Przeglądane są wszystkie podciągi dla ale bezpośrednie porównania podciągu z (które jest bardzo kosztowne) ma miejsce tylko wtedy, gdy Oczekiwana złożoność obliczeniowa jest rzędu (pl)
- Алгоритм Рабина — Карпа — это алгоритм поиска строки, который ищет шаблон, то есть подстроку, в тексте, используя хеширование. Он был разработан в 1987 году Майклом Рабином и Ричардом Карпом. Алгоритм редко используется для поиска одиночного шаблона, но имеет значительную теоретическую важность и очень эффективен в поиске совпадений множественных шаблонов одинаковой длины. Для текста длины n и шаблона длины m его среднее и лучшее время исполнения равно O(n) при правильном выборе хеш-функции (смотрите ниже), но в худшем случае он имеет эффективность O(nm), что является одной из причин того, почему он не слишком широко используется. Для приложений, в которых допустимы ложные срабатывания при поиске, то есть, когда некоторые из найденных вхождений шаблона на самом деле могут не соответствоват (ru)
|
![[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)