| dbo:abstract
|
- Der Knuth-Morris-Pratt-Algorithmus wurde nach Donald Ervin Knuth, James Hiram Morris und Vaughan Pratt benannt und ist ein String-Matching-Algorithmus. Seine asymptotische Laufzeit ist linear in der Länge des Musters (auch Suchbegriff, Suchmaske), nach dem gesucht wird, plus der Länge des durchsuchten Textes. Pratt entwickelte 1970 die Grundidee unabhängig von Knuth (der etwas später darauf stieß), und Pratt und Morris veröffentlichten 1970 einen Technischen Bericht dazu. Schließlich veröffentlichten alle drei 1977 einen Aufsatz dazu. (de)
- El algoritmo KMP es un algoritmo de búsqueda de subcadenas simple. Por lo tanto su objetivo es buscar la existencia de una subcadena (habitualmente llamada patrón) dentro de otra cadena. La búsqueda se lleva a cabo utilizando información basada en los fallos previos. Información obtenida del propio patrón creando previamente una tabla de valores sobre su propio contenido. El objetivo de crear dicha tabla es poder determinar donde podría darse la siguiente existencia, sin necesidad de analizar más de 1 vez los caracteres de la cadena donde se busca. En 1970 S.A. Cook sugirió la existencia de un algoritmo que resuelve la búsqueda en un tiempo equivalente a M+N, en el peor caso, a raíz de unos resultados teóricos que obtuvo mientras probaba un tipo de máquina abstracta. Knuth y Pratt siguiendo los pasos que Cook usó para probar su teorema, lograron crear el algoritmo que lleva sus nombres. De modo independiente mientras trabajaba en un editor de texto acabó descubriendo el mismo algoritmo, para satisfacer la cuestión de la búsqueda eficiente de subcadenas, y que publicaron juntos los tres en 1976. (es)
- In computer science, the Knuth–Morris–Pratt string-searching algorithm (or KMP algorithm) searches for occurrences of a "word" W within a main "text string" S by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters. The algorithm was conceived by James H. Morris and independently discovered by Donald Knuth "a few weeks later" from automata theory.Morris and Vaughan Pratt published a technical report in 1970.The three also published the algorithm jointly in 1977. Independently, in 1969, Matiyasevich discovered a similar algorithm, coded by a two-dimensional Turing machine, while studying a string-pattern-matching recognition problem over a binary alphabet. This was the first linear-time algorithm for string matching. (en)
- Algoritme Knuth-Morris-Pratt adalah salah satu algoritme pencarian string, dikembangkan secara terpisah oleh Donald E. Knuth pada tahun 1967 dan bersama pada tahun 1966, tetapi keduanya mempublikasikannya secara bersamaan pada tahun 1977. Jika kita melihat algoritme brute force lebih mendalam, kita mengetahui bahwa dengan mengingat beberapa perbandingan yang dilakukan sebelumnya kita dapat meningkatkan besar pergeseran yang dilakukan. Hal ini akan menghemat perbandingan, yang selanjutnya akan meningkatkan kecepatan pencarian. (in)
- L'algorithme de Knuth-Morris-Pratt (ou d'une manière plus courte l'algorithme KMP) est un algorithme de recherche de sous-chaîne (de caractères), permettant de trouver les occurrences d'une chaîne dans un texte avec une complexité linéaire dans le pire cas. Sa particularité réside en un pré-traitement de la chaîne, qui fournit une information suffisante pour déterminer où continuer la recherche en cas de non-correspondance. Ainsi l'algorithme ne ré-examine pas les caractères qui ont été vus précédemment, et donc limite le nombre de comparaisons nécessaires. L'algorithme a été conçu en 1970 par Knuth et (en), et dans un autre contexte, par (en), et publié conjointement en 1977. Indépendamment Matiyasevich avait déjà obtenu dès 1969 un algorithme similaire, codé par une machine de Turing à deux dimensions, en étudiant un problème de reconnaissance d'occurrence de chaîne. (fr)
- 컴퓨터 과학에서 커누스-모리스-프랫 알고리즘(Knuth–Morris–Pratt algorithm, KMP)은 문자열 중에 특정 패턴을 찾아내는 문자열 검색 알고리즘의 하나이다. 문자열 검색시 불필요한 문자간 비교를 없애기 위해 실패함수 (pi)를 사용한다. vector KMP_GET(string grope){ int Begin=0, Length = (int)grope.size; vector pi(Length, 0); for(int i=1 ; i< Length ; i++){ while(grope[i] != grope[Begin] && Begin > 0)Begin = pi[Begin-1]; if(grope[i] == grope[Begin]) pi[i] = ++Begin; } return pi;} 위는 실패함수를 계산하는 코드이다. 위 코드로 나온 pi배열 KMP알고리즘 실행중, 일치하지 않는 문자가 있을 때 어디서부터 검색을 해야할지(몇칸을 뛰어넘어야 하는지) 알려주는 지표같은 존재이다. (ko)
- L'algoritmo di Knuth-Morris-Pratt (spesso abbreviato come algoritmo KMP) è un algoritmo di pattern matching su stringhe, che permette di trovare le occorrenze di una stringa (pattern) in un testo . La sua peculiarità risiede nel pretrattamento della stringa da cercare, la quale contiene l'indicazione sufficiente a determinare la posizione da cui continuare la ricerca in caso di non-corrispondenza. Questo permette all'algoritmo di non riesaminare i caratteri che erano stati precedentemente verificati, e dunque di limitare il numero di confronti necessari. L'algoritmo è stato inventato da Knuth e , e indipendentemente da nel 1975. (it)
- クヌース–モリス–プラット法（Knuth–Morris–Pratt algorithm、KMP法と略記）とは、文字列検索アルゴリズムの一種。テキスト（文字列）Sから単語Wを探すにあたり、不一致となった位置と単語自身の情報から次に照合を試すべき位置を決定することで検索を効率化するアルゴリズムである。 このアルゴリズムは1977年、ドナルド・クヌースと Vaughan Pratt および（単独で）J. H. Morris が発明し、3人共同で発表した。 本項目では文字列を表すにあたって、0 からインデックスを開始する配列を用いる。従って（後述の）単語 W 内の文字 'C' は W[2] と表される。 (ja)
- Algorytm Knutha-Morrisa-Pratta – algorytm wyszukiwania wzorca w tekście. Algorytm wykorzystuje fakt, że w przypadku wystąpienia niezgodności ze wzorcem, sam wzorzec zawiera w sobie informację pozwalającą określić, gdzie powinna się zacząć kolejna próba dopasowania, pomijając ponowne porównywanie już dopasowanych znaków. Dzięki temu właściwy algorytm działa w okresie liniowym względem długości przeszukiwanego tekstu i wzorca. Ma to znaczenie dla dużych wzorców. Algorytm został wynaleziony przez Donalda Knutha i Vaughana Pratta i niezależnie przez w 1977, ale wszyscy trzej opublikowali go wspólnie. (pl)
- O algoritmo de Knuth–Morris–Pratt procura a ocorrência de uma "palavra" W dentro de um "texto" S empregando a simples técnica de que quando aparece uma diferença, a palavra tem em si a informação necessária para determinar onde começar a próxima comparação. O algoritmo foi inventado por Donald Knuth e Vaughan Pratt e independentemente por James Morris em 1977, embora os três tenham-no publicado conjuntamente. Exemplo: abcdabd 0 - sempre começa com 0 00 - na substring "ab" não há prefixo e sufixo próprios iguais 000 - idem para "abc" 0000 - idem para "abcd" 00001 - na substring "abcda", o prefixo próprio "a", que inicia a substring, é igual ao sufixo próprio "a", que termina a substring 000012 - na substring "abcdab", o prefixo próprio "ab", que inicia a substring, é igual ao sufixo próprio "ab", que termina a substring 0000120 - na substring "abcdabd" não há prefixo e sufixo próprios iguais (pt)
- Алгоритм Кнута — Морриса — Пратта (КМП-алгоритм) — эффективный алгоритм, осуществляющий поиск подстроки в строке. Время работы алгоритма линейно зависит от объёма входных данных, то есть разработать асимптотически более эффективный алгоритм невозможно. Алгоритм был разработан Д. Кнутом и В. Праттом и, независимо от них, Д. Моррисом. Результаты своей работы они опубликовали совместно в 1977 году. (ru)
- 在计算机科学中，Knuth-Morris-Pratt字符串查找算法（简称为KMP算法）可在一个字符串S内查找一个词W的出现位置。一个词在不匹配时本身就包含足够的信息来确定下一个匹配可能的开始位置，此算法利用这一特性以避免重新检查先前配對的字符。 这个算法由高德纳和在1974年构思，同年也独立地设计出该算法，最终三人于1977年联合发表。 (zh)
- Алгоритм Кнута — Морріса — Пратта (скорочено алгоритм КМП) — один із алгоритмів пошуку рядка, що шукає входження слова W у рядку S, використовуючи просте спостереження, що коли відбувається невідповідність, то слово містить у собі достатньо інформації для того, щоб визначити, де наступне входження може початися, таким чином пропускаючи кількаразову перевірку попередньо порівняних символів. Алгоритм, що винайшли Дональд Кнут та , а також незалежно від них , опубліковано у спільній статті у 1977 році. Часова асимптотична складність алгоритму становить O(N+M), де N — довжина слова W, M — довжина рядка S. (uk)
|
| rdfs:comment
|
- Der Knuth-Morris-Pratt-Algorithmus wurde nach Donald Ervin Knuth, James Hiram Morris und Vaughan Pratt benannt und ist ein String-Matching-Algorithmus. Seine asymptotische Laufzeit ist linear in der Länge des Musters (auch Suchbegriff, Suchmaske), nach dem gesucht wird, plus der Länge des durchsuchten Textes. Pratt entwickelte 1970 die Grundidee unabhängig von Knuth (der etwas später darauf stieß), und Pratt und Morris veröffentlichten 1970 einen Technischen Bericht dazu. Schließlich veröffentlichten alle drei 1977 einen Aufsatz dazu. (de)
- Algoritme Knuth-Morris-Pratt adalah salah satu algoritme pencarian string, dikembangkan secara terpisah oleh Donald E. Knuth pada tahun 1967 dan bersama pada tahun 1966, tetapi keduanya mempublikasikannya secara bersamaan pada tahun 1977. Jika kita melihat algoritme brute force lebih mendalam, kita mengetahui bahwa dengan mengingat beberapa perbandingan yang dilakukan sebelumnya kita dapat meningkatkan besar pergeseran yang dilakukan. Hal ini akan menghemat perbandingan, yang selanjutnya akan meningkatkan kecepatan pencarian. (in)
- 컴퓨터 과학에서 커누스-모리스-프랫 알고리즘(Knuth–Morris–Pratt algorithm, KMP)은 문자열 중에 특정 패턴을 찾아내는 문자열 검색 알고리즘의 하나이다. 문자열 검색시 불필요한 문자간 비교를 없애기 위해 실패함수 (pi)를 사용한다. vector KMP_GET(string grope){ int Begin=0, Length = (int)grope.size; vector pi(Length, 0); for(int i=1 ; i< Length ; i++){ while(grope[i] != grope[Begin] && Begin > 0)Begin = pi[Begin-1]; if(grope[i] == grope[Begin]) pi[i] = ++Begin; } return pi;} 위는 실패함수를 계산하는 코드이다. 위 코드로 나온 pi배열 KMP알고리즘 실행중, 일치하지 않는 문자가 있을 때 어디서부터 검색을 해야할지(몇칸을 뛰어넘어야 하는지) 알려주는 지표같은 존재이다. (ko)
- クヌース–モリス–プラット法（Knuth–Morris–Pratt algorithm、KMP法と略記）とは、文字列検索アルゴリズムの一種。テキスト（文字列）Sから単語Wを探すにあたり、不一致となった位置と単語自身の情報から次に照合を試すべき位置を決定することで検索を効率化するアルゴリズムである。 このアルゴリズムは1977年、ドナルド・クヌースと Vaughan Pratt および（単独で）J. H. Morris が発明し、3人共同で発表した。 本項目では文字列を表すにあたって、0 からインデックスを開始する配列を用いる。従って（後述の）単語 W 内の文字 'C' は W[2] と表される。 (ja)
- Алгоритм Кнута — Морриса — Пратта (КМП-алгоритм) — эффективный алгоритм, осуществляющий поиск подстроки в строке. Время работы алгоритма линейно зависит от объёма входных данных, то есть разработать асимптотически более эффективный алгоритм невозможно. Алгоритм был разработан Д. Кнутом и В. Праттом и, независимо от них, Д. Моррисом. Результаты своей работы они опубликовали совместно в 1977 году. (ru)
- 在计算机科学中，Knuth-Morris-Pratt字符串查找算法（简称为KMP算法）可在一个字符串S内查找一个词W的出现位置。一个词在不匹配时本身就包含足够的信息来确定下一个匹配可能的开始位置，此算法利用这一特性以避免重新检查先前配對的字符。 这个算法由高德纳和在1974年构思，同年也独立地设计出该算法，最终三人于1977年联合发表。 (zh)
- El algoritmo KMP es un algoritmo de búsqueda de subcadenas simple. Por lo tanto su objetivo es buscar la existencia de una subcadena (habitualmente llamada patrón) dentro de otra cadena. La búsqueda se lleva a cabo utilizando información basada en los fallos previos. Información obtenida del propio patrón creando previamente una tabla de valores sobre su propio contenido. El objetivo de crear dicha tabla es poder determinar donde podría darse la siguiente existencia, sin necesidad de analizar más de 1 vez los caracteres de la cadena donde se busca. (es)
- In computer science, the Knuth–Morris–Pratt string-searching algorithm (or KMP algorithm) searches for occurrences of a "word" W within a main "text string" S by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters. (en)
- L'algorithme de Knuth-Morris-Pratt (ou d'une manière plus courte l'algorithme KMP) est un algorithme de recherche de sous-chaîne (de caractères), permettant de trouver les occurrences d'une chaîne dans un texte avec une complexité linéaire dans le pire cas. Sa particularité réside en un pré-traitement de la chaîne, qui fournit une information suffisante pour déterminer où continuer la recherche en cas de non-correspondance. Ainsi l'algorithme ne ré-examine pas les caractères qui ont été vus précédemment, et donc limite le nombre de comparaisons nécessaires. (fr)
- L'algoritmo di Knuth-Morris-Pratt (spesso abbreviato come algoritmo KMP) è un algoritmo di pattern matching su stringhe, che permette di trovare le occorrenze di una stringa (pattern) in un testo . La sua peculiarità risiede nel pretrattamento della stringa da cercare, la quale contiene l'indicazione sufficiente a determinare la posizione da cui continuare la ricerca in caso di non-corrispondenza. Questo permette all'algoritmo di non riesaminare i caratteri che erano stati precedentemente verificati, e dunque di limitare il numero di confronti necessari. (it)
- Algorytm Knutha-Morrisa-Pratta – algorytm wyszukiwania wzorca w tekście. Algorytm wykorzystuje fakt, że w przypadku wystąpienia niezgodności ze wzorcem, sam wzorzec zawiera w sobie informację pozwalającą określić, gdzie powinna się zacząć kolejna próba dopasowania, pomijając ponowne porównywanie już dopasowanych znaków. Dzięki temu właściwy algorytm działa w okresie liniowym względem długości przeszukiwanego tekstu i wzorca. Ma to znaczenie dla dużych wzorców. (pl)
- O algoritmo de Knuth–Morris–Pratt procura a ocorrência de uma "palavra" W dentro de um "texto" S empregando a simples técnica de que quando aparece uma diferença, a palavra tem em si a informação necessária para determinar onde começar a próxima comparação. O algoritmo foi inventado por Donald Knuth e Vaughan Pratt e independentemente por James Morris em 1977, embora os três tenham-no publicado conjuntamente. Exemplo: (pt)
- Алгоритм Кнута — Морріса — Пратта (скорочено алгоритм КМП) — один із алгоритмів пошуку рядка, що шукає входження слова W у рядку S, використовуючи просте спостереження, що коли відбувається невідповідність, то слово містить у собі достатньо інформації для того, щоб визначити, де наступне входження може початися, таким чином пропускаючи кількаразову перевірку попередньо порівняних символів. Алгоритм, що винайшли Дональд Кнут та , а також незалежно від них , опубліковано у спільній статті у 1977 році. (uk)
|
