| dbo:abstract
|
- 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)
- في عام 1987 قام الباحثان ريتشارد م. كارب ومايكل أ. رابين بإنشاء خوارزمية بحث في النصوص سُميت باسم خوارزمية رابين – كارب أو خوارزمية كارب – رابين. وهي تُعد من الخوارزميات المشهورة في علم الحاسوب. تستخدم هذه الخوارزمية مبدءًا من مبادئ التجزئة (hashing) لإيجاد تطابق تام لسلسلة من الرموز (string) في نص وهو التجزئة المتدرجة (rolling hash). باستخدام التجزئة المتدرجة تقوم الخوارزمية بشكل سريع باستثناء مواقع من النص لا يُمكن مطابقتها للسلسلة المراد البحث عنها، وتكتفي بالبحث ضمن المواقع المتبقية عن التطابق المطلوب. من الممكن تعميم فكرة الخوارزمية للبحث عن أكثر من تطابق واحد للسلسلة في نفس النص، أو البحث عن تطابق لعدة سلاسل مختلفة فيه. يتم حساب معدل الوقت المتوقع (expected time) الذي تحتاجه الخوارزمية لإيجاد تطابق واحد لسلسة من الرموز في نص عن طريق إيجاد مجموع أطوال السلسلة والنص معًا، مما يُعد وقتًا خطيًّا (linear). أما بالنسبة للتعقيد الزمني الأسوأ (worst-case time complexity) فيُحسب كحاصل ضرب هذين الطولين. أما في حالة إيجاد عدة تطابقات للسلسلة، فتحتاج الخوارزمية، بالمعدل، وقتًا خطيًّا بالاعتماد على طول المدخلات، ويضاف إليه أطوال كل التطابقات مما يجعل معدل الوقت المتوقع يتعدّى الوقت الخطي. وفي المقابل، نجد خوارزمية أخرى، وهي خوارزمية أهو – كوراسيك (Aho-Corasick algorithm)، تستطيع بدورها إيجاد جميع حالات التطابق لأكثر من سلسلة في النص بتعقيد خطّي للزمن والمساحة الأسوأ بالاعتماد على طول المدخلات وعدد التطابقات التي تم إيجادها، وليس مجموع أطوال التطابقات. تُعد عملية اكتشاف الانتحال العلمي إحدى التطبيقات المهمة لخوارزمية رابين – كارب. بوجود مصادر متعددة للبحث العلمي، تقوم الخوارزمية وبشكل سريع بالمرور على الجُمل في الورقة البحثية المراد التحقق من أصالتها، والبحث عن مطابقة هذه الجمل في المصادر المتوفرة. وبالتأكيد، ستقوم الخوارزمية بتجاهل علامات الترقيم، والتشكيل في حالة اللغة العربية، والأحرف الكبيرة والصغيرة في حالة اللغة الإنجليزية عند البحث. في هذه الحالة، لن يكفي، من الناحية العملية، تطبيق الخوارزمية للبحث عن سلسلة واحدة من الرموز، وذلك لغزارة السلاسل (الجمل) المراد البحث عنها ومطابقتها إن وُجدت. (ar)
- 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 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. Eine Professorin 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. (de)
- 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. La función hash tiene la forma donde es un número primo grande que será el tamaño de la tabla de dispersión y se calcula de la forma indicada más abajo. Para transformar cada subcadena de caracteres en un entero lo que hacemos es representar los caracteres en una base que en el planteamiento original coincide con el tamaño del alfabeto. Por tanto el entero correspondiente a la subcadena de texto sería: xi=Ci×Bm-1+Ci-1×Bm-2+...+Ci+m-1 podemos calcular el valor de en función de . xi+1=xi×B-Ci×Bm+Ci+m Es decir, si la cadena es un número en base B, el nuevo valor será el resultado de multiplicar por la base el valor anterior eliminado el dígito de mayor peso (ya que no está en la cadena) y añadiendo como componente de menor peso el valor del nuevo símbolo. Siguiendo este planteamiento, y dependiendo de la longitud del patrón, el podría superar el rango de enteros representable por el computador. Para que esto no suceda se usa la función módulo (resto de la división). Como la función módulo es asociativa, podemos calcular el incrementalmente a partir de cada . Ejemplo de Implementación
* En el lenguaje de programación Julia. (es)
- 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)
- 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. To find a single match of a single pattern, the expected time of the algorithm is linear in the combined length of the pattern and text,although its worst-case time complexity is the product of the two lengths. To find multiple matches, the expected time is linear in the input lengths, plus the combined length of all the matches, which could be greater than linear. In contrast, the Aho–Corasick algorithm can find all matches of multiple patterns in worst-case time and space linear in the input length and the number of matches (instead of the total length of the matches). A practical application of the algorithm is detecting plagiarism. Given source material, the algorithm 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. (en)
- ラビン-カープ文字列検索アルゴリズム（英: Rabin-Karp string search algorithm）は、マイケル・ラビンとリチャード・カープが開発した、ハッシュ関数を利用してテキストからパターン（サブ文字列）を探す文字列検索アルゴリズムの一種。1つのパターンの検索にはあまり用いられないが、理論的には重要であり、複数パターンの検索には効果的である。テキストの文字数が n、パターンの文字数が m とした場合、平均および最良の実行時間はO(n)だが、ごくまれに最悪性能として O(nm)となる（広く用いられないのはそのため）。しかし、k個の文字列のいずれかにマッチする部分を検索するのに要する時間は k によらず平均で O(n) となるという独特の利点を持つ。以下、単にラビン-カープまたはラビン-カープ法と略記することがある。 ラビン-カープの単純な応用例として、盗作の検出がある。例えば、学生が『白鯨』に関する英語の論文を書いたとしよう。賢い教授は『白鯨』に関する様々な資料を集め、それらの全文を自動的に抽出するものとする。そこで、ラビン-カープを使えば学生の論文の任意の文がそれら資料からの丸写しかどうかを判定できる。微妙な修正で盗作を判定できなくなるのを防ぐには、大文字・小文字の別を無視し、句読点を無視すればよい。この場合の検索文字列数 k は膨大なので、単一文字列検索アルゴリズムは非現実的である。 (ja)
- 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. L'algoritmo può essere generalizzato per la ricerca simultanea di pattern multipli nello stesso testo. Nella ricerca di un singolo pattern è efficiente in pratica, ma ha una complessità al caso pessimo superiore ad altri algoritmi come quelli di Knut-Morris-Pratt, e Boyer-Moore. (it)
- 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 O efektywności algorytmu decyduje konstrukcja funkcji mieszającej – powinna istnieć funkcja która niskim kosztem wyznacza na podstawie znanej już wartości 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 Pseudokod (dane ): for to dobeginif thenbeginporównaj ciąg z podciągiem if wynik porównania prawdziwy then zwróć indeks endend (pl)
- Алгоритм Рабина — Карпа — это алгоритм поиска строки, который ищет шаблон, то есть подстроку, в тексте, используя хеширование. Он был разработан в 1987 году Майклом Рабином и Ричардом Карпом. Алгоритм редко используется для поиска одиночного шаблона, но имеет значительную теоретическую важность и очень эффективен в поиске совпадений множественных шаблонов одинаковой длины. Для текста длины n и шаблона длины m его среднее и лучшее время исполнения равно O(n) при правильном выборе хеш-функции (смотрите ниже), но в худшем случае он имеет эффективность O(nm), что является одной из причин того, почему он не слишком широко используется. Для приложений, в которых допустимы ложные срабатывания при поиске, то есть, когда некоторые из найденных вхождений шаблона на самом деле могут не соответствовать шаблону, алгоритм Рабина — Карпа работает за гарантированное время O(n) и при подходящем выборе рандомизированной хеш-функции (смотрите ниже) вероятность ошибки можно сделать очень малой. Также алгоритм имеет уникальную особенность находить любую из заданных k строк одинаковой длины в среднем (при правильном выборе хеш-функции) за время O(n) независимо от размера k. Одно из простейших практических применений алгоритма Рабина — Карпа состоит в определении плагиата. Скажем, например, что студент пишет работу по Моби Дику. Коварный профессор находит различные исходные материалы по Моби Дику и автоматически извлекает список предложений в этих материалах. Затем алгоритм Рабина — Карпа может быстро найти в проверяемой статье примеры вхождения некоторых предложений из исходных материалов. Для устранения чувствительности алгоритма к небольшим различиям можно игнорировать детали, такие как регистр или пунктуация, при помощи их удаления. Поскольку количество строк, которые мы ищем, k, очень большое, обычные алгоритмы поиска одиночных строк становятся неэффективными. (ru)
- 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)
|
| 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)
|
