| dbo:abstract
|
- Algoritmus Aho-Corasick je vynalezený Alfredem Ahem a . Je to druh slovníkového vyhledávacího algoritmu, který ve vstupním textu hledá prvky konečné množiny řetězců. Vyhledává všechny prvky množiny najednou, jeho asymptotická složitost je proto lineární k délce všech vyhledávaných prvků plus délce vstupního textu plus délce výstupu. Jelikož algoritmus najde všechny výskyty, celkový počet výskytů pro celou množinu může být až kvadratický (například v případě, kdy vyhledávané řetězce jsou a, aa, aaa, aaaa a vstupní text je aaaa). Neformálně řečeno, algoritmus konstruuje trie se zpětnými odkazy pro každý vrchol (například abc) na nejdelší vlastní sufix (pokud existuje, tak bc, jinak pokud existuje c, jinak do kořene). Obsahuje také odkazy z každého vrcholu na prvek slovníku obsahující odpovídající nejdelší sufix. Tudíž všechny výsledky mohou být vypsány procházením výsledného spojového seznamu. Algoritmus pak pracuje tak, že postupně zpracovává vstupní řetězec a pohybuje se po nejdelší odpovídající cestě stromu. Pokud algoritmus načte znak, který neodpovídá žádné další možné cestě, přejde po zpětném odkazu na nejdelší odpovídající sufix a pokračuje tam (případně opět přejde zpět). Pokud je množina vyhledávaných řetězců známa předem (např. databáze počítačových virů), je možné zkonstruovat automat předem a ten pak uložit. (cs)
- Der Aho-Corasick-Algorithmus ist ein String-Matching-Algorithmus, der von Alfred V. Aho und 1975 entwickelt wurde. Der Algorithmus führt eine Art Wörterbuch-Vergleich durch, bei dem die Eingabe effizient nach vorher festgelegten Signaturen durchsucht wird. Dabei wird kein Zeichen der Eingabe mehr als einmal gelesen.Das Verfahren ist dann besonders effizient, wenn sich die Signaturen überlappen, d. h. in Präfix- und Suffix-Beziehungen stehen (z. B. {„Igel“, „Geld“, „Eldorado“}).Der Aho-Corasick-Algorithmus besteht aus zwei Phasen: 1.
* Zunächst erzeugt der Algorithmus auf Basis der gegebenen bzw. gewünschten Wörterbuchmenge eine Trie-Struktur, die auch als endlicher Zustandsautomat interpretiert werden kann. Jedem Zustand wird eine Ausgabemenge zugeordnet, die zunächst leer ist. Für jeden Zustand, bei dem ein Suchwort endet, wird dieses Suchwort seiner Ausgabemenge hinzugefügt. 2.
* In der zweiten Phase werden die Knoten oder Zustände des Tries paarweise disjunkt nummeriert und eine Fehlerfunktion berechnet. Die Funktion ist für jeden Knoten definiert und legt fest, in welchem Zustand die Verarbeitung fortgesetzt wird, falls das gerade gelesene Zeichen der Eingabe keinen regulär gültigen Zustandsübergang bewirkt. Dadurch wird es möglich, schnell zwischen bereits erkannten Teilsignaturen zu wechseln und die Erkennung fortzusetzen, ohne den Automaten neu starten zu müssen. (de)
- In computer science, the Aho–Corasick algorithm is a string-searching algorithm invented by Alfred V. Aho and Margaret J. Corasick in 1975. It is a kind of dictionary-matching algorithm that locates elements of a finite set of strings (the "dictionary") within an input text. It matches all strings simultaneously. The complexity of the algorithm is linear in the length of the strings plus the length of the searched text plus the number of output matches. Note that because all matches are found, there can be a quadratic number of matches if every substring matches (e.g. dictionary = a, aa, aaa, aaaa and input string is aaaa). Informally, the algorithm constructs a finite-state machine that resembles a trie with additional links between the various internal nodes. These extra internal links allow fast transitions between failed string matches (e.g. a search for cat in a trie that does not contain cat, but contains cart, and thus would fail at the node prefixed by ca), to other branches of the trie that share a common prefix (e.g., in the previous case, a branch for attribute might be the best lateral transition). This allows the automaton to transition between string matches without the need for backtracking. When the string dictionary is known in advance (e.g. a computer virus database), the construction of the automaton can be performed once off-line and the compiled automaton stored for later use. In this case, its run time is linear in the length of the input plus the number of matched entries. The Aho–Corasick string-matching algorithm formed the basis of the original Unix command fgrep. (en)
- L'algorithme d'Aho-Corasick est un algorithme de recherche de chaîne de caractères (ou motif) dans un texte dû à Alfred Aho et et publié en 1975. L'algorithme consiste à avancer dans une structure de données abstraite appelée dictionnaire qui contient le ou les mots recherchés en lisant les lettres du texte T une par une. La structure de données est implantée de manière efficace, ce qui garantit que chaque lettre du texte n'est lue qu'une seule fois. Généralement le dictionnaire est implanté à l'aide d'une trie ou arbre préfixe auquel on rajoute des liens suffixes. Une fois le dictionnaire implanté, l'algorithme a une complexité linéaire en la taille du texte T et des chaînes recherchées. L'algorithme extrait toutes les occurrences des motifs. Il est donc possible que le nombre d'occurrences soit quadratique, comme pour un dictionnaire a, aa, aaa, aaaa et un texte aaaa. Le motif a apparaît à quatre reprises, le motif aa à trois reprises, etc. (fr)
- En Ciencias de la Computación, el Algoritmo de búsqueda de cadenas Aho–Corasick es un algoritmo de búsqueda de cadenas inventado por Alfred V. Aho y Margaret J. Corasick. Es un algoritmo que busca elementos (patrones) de un conjunto finito de cadenas (diccionario) dentro de un texto. Una de las ventajas que presenta es que procesa el texto de entrada solamente una vez, es decir, realiza la búsqueda de todos los patrones de forma simultánea. Si se considera el tamaño del alfabeto al cual pertenecen los patrones como constante, entonces la complejidad temporal del algoritmo es lineal en cuanto a la suma de las longitudes de los patrones más la longitud del texto. Si además se quieren conocer todas las ocurrencias de forma explícita, al orden del algoritmo hay que sumarle la cantidad de ocurrencias. Es necesario destacar que si se buscan todas las ocurrencias, entonces puede haber un número cuadrático de ellas si cada subcadena es una ocurrencia. Por ejemplo si el diccionario es a, aa, aaa, aaaa y la cadena de entrada es aaaa). Informalmente, el algoritmo construye un autómata finito determinista similar a un trie con enlaces adicionales entre los nodos internos. Estos enlaces extras permiten llevar a cabo transiciones bastante rápidas entre correspondencias fallidas de patrones (ejemplo, una búsqueda para cat en un trie que no contiene a cat, pero contiene cart, y de esta manera fallaría en el nodo prefijado por ca), a otras ramificaciones del trie que comparten prefijos comunes (ejemplo, en el caso anterior, una ramificación para attribute pudiera ser la mejor transición a efectuar). Esto le permite al autómata realizar transiciones entre ocurrencias de patrones sin necesidad de backtracking. Cuando el diccionario de patrones se conoce de antemano (por ejemplo, en una base de datos de virus), la construcción del autómata se puede llevar a cabo y se guarda el autómata compilado para uso futuro. En este caso, la complejidad temporal es lineal en cuanto a la longitud de la entrada más el número de entradas encontradas. El gráfico que se muestra a continuación es la estructura Aho-Corasick construida a partir del diccionario especificado, con cada fila en la tabla representando un nodo en el trie, y la columna Camino indicando la (única) secuencia de caracteres desde la raíz del trie al nodo en cuestión. La estructura de datos tiene un nodo para cada prefijo de cada cadena en el diccionario. De esta manera, si (bca) está en el diccionario, entonces estarán presentes nodos para (bca), (bc), (b) y. Hay un arco dirigido "hijo" negro desde cada nodo a un nodo cuyo Camino se obtiene añadiendo un carácter. Por lo tanto, hay un arco negro de (bc) a (bca). Hay un arco dirigido "sufijo" de cada nodo al nodo correspondiente a su sufijo propio más largo en el grafo. Por ejemplo, para el nodo (caa), su sufijos propios son (aa), (a) y. El más largo de estos que existe en el grafo es (a), por lo que hay un arco azul de (caa) a (a). Hay un arco verde "sufijo en diccionario" desde cada nodo al siguiente nodo en el diccionario que puede ser alcanzado siguiendo arcos azules. Por ejemplo, hay un arco verde de (bca) a (a) porque (a) es el primer nodo correspondiente a uno de los patrones en el diccionario (nodo blanco) que se alcanza siguiendo los arcos azules a (ca) y luego a (a). A la hora de encontrar las occurrencias en un texto, en cada paso el nodo actual se extiende encontrando su hijo con el carácter correspondiente, y si no existe, se busca su "hijo sufijo" utilizado en enlace sufijo y se continúa de esta manera hasta encontrar un nodo que tenga una transición con el carácter actual o hasta que se llegue al nodo raíz. Cuando el algoritmo alcanza un nodo, devuelve todas las entradas en el diccionario que terminan en la posición del carácter actual en el texto de entrada. Esto se hace imprimiendo cada nodo alcanzado siguiendo los "enlaces sufijo en diccionario", comenzando por ese nodo, y continuando hasta alcanzar un nodo que no tenga "enlace sufijo en diccionario". La ejecución con la cadena de entrada abccab produce los siguientes pasos: (es)
- エイホ–コラシック法（英: Aho–Corasick algorithm）とは、1975年にアルフレッド・エイホと Margaret J. Corasick が発見した文字列探索アルゴリズムである。 (ja)
- 아호 코라식 알고리즘(Aho–Corasick string matching algorithm)은 Alfred V. Aho와 Margaret J. Corasick이 고안한 문자열 검색 알고리즘(매칭 알고리즘)이다. 패턴 1개를 탐색하는 매칭 알고리즘은 선형 시간에 구현됨을 KMP 등 여러 알고리즘을 통하여 증명되었다. 하지만 패턴 집합에 대하여 이러한 알고리즘을 수행하게 되면 패턴 개수에 비례하여 그 속도가 느려지게 된다. 즉, 의 시간 복잡도를 가지게 된다.(: 모든 패턴들의 길이 합, : 패턴 수, : text 크기) 하지만 Aho-Corasick 알고리즘을 이용하면 의 시간 복잡도로 패턴 집합에 대하여 패턴 길이와 텍스트의 선형 시간에 탐색을 처리할 수 있게 된다.(k: 텍스트 내에 패턴의 발생 수) 이러한 Aho-Corasick 알고리즘을 구현하기 위하여 Keyword Tree, Failure link, Output link 자료구조를 사용하여야 한다. (ko)
- Algorytm Aho-Corasick jest jednym z algorytmów wyszukiwania wzorca w tekście opracowanym przez Alfreda V. Aho oraz . Znajduje on w tekście wystąpienia słów ze słownika (pewnego zadanego zbioru wzorców). Wszystkie wzorce są szukane jednocześnie, co powoduje, że złożoność obliczeniowa algorytmu jest liniowa względem sumy długości wzorców, długości tekstu i liczby wystąpień wzorców w tekście. W tekście może jednak występować nawet kwadratowa od długości tekstu liczba wystąpień wzorców (np. gdy słownikiem jest a, aa, aaa, aaaa, zaś tekstem jest aaaa). Ideą algorytmu jest stworzenie Drzewa trie o sufiksowych połączeniach pomiędzy wierzchołkami reprezentującymi różne słowa (niekoniecznie znajdujące się w słowniku). Inaczej mówiąc tworzone jest drzewo o etykietowanych krawędziach w którym każdy wierzchołek reprezentuje pewne słowo, składające się ze złączonych etykiet krawędzi znajdujących się na ścieżce od korzenia do tego węzła. Dodatkowo dołączane są krawędzie od wierzchołka do innego wierzchołka reprezentującego jego najdłuższy sufiks (tzw. fail) W czasie wyszukiwania w tekście algorytm porusza się po tym drzewie zaczynając od korzenia i przechodząc do wierzchołka po krawędzi etykietowanej znakiem odczytanym z tekstu. W przypadku gdy takiej nie ma w drzewie, algorytm korzysta z krawędzi fail i tam próbuje przejść do wierzchołka po krawędzi etykietowanej odczytanym znakiem. W przypadku natrafienia na węzeł oznaczony jako koniec słowa, algorytm wypisuje je jako znalezione w tekście oraz sprawdza, czy czasem w tym miejscu nie kończy się więcej wzorców przechodząc krawędziami fail aż do korzenia, sprawdzając, czy nie przechodzi po wierzchołku będącym końcem wzorca. Jednym z programów wykorzystujących ten algorytm jest polecenie systemu Unix – fgrep. Przykładowy słownik oraz drzewo trie (szare węzły odpowiadają słowom niewystępującym w słowniku, niebieskie krawędzie wskazują najdłuższy sufiks słowa). Opis wyszukiwania wzorców w tekście abccab (pl)
- O algoritmo de Aho-Corasick é um algoritmo de pesquisa em strings inventado por Alfred V. Aho e , ambos pesquisadores do Bell Labs, em 1975. O objetivo do algoritmo é localizar todas as palavras chaves em textos, a partir de uma única interação, utilizando para tanto um dicionário contendo um conjunto finito de palavras chaves. A complexidade do algoritmo é linear Uma outra abordagem para este problema, seria utilizar um Algoritmo guloso, que faria a iteração de palavra por palavra comparando com as chaves existentes no dicionário. Esta técnica não seria aplicável a grandes dicionários por ser muito lenta - complexidade , onde nc é o número de palavras chaves e np é o número de palavras. (pt)
- Алгоритм Ахо — Корасик — алгоритм поиска подстроки, разработанный Альфредом Ахо и в 1975 году, реализует поиск множества подстрок из словаря в данной строке. Широко применяется в системном программном обеспечении, например, используется в утилите поиска grep. (ru)
- 在计算机科学中，Aho–Corasick算法是由Alfred V. Aho和Margaret J.Corasick 发明的字符串搜索算法，用于在输入的一串字符串中匹配有限组“字典”中的子串。它与普通字符串匹配的不同点在于同时与所有字典串进行匹配。算法均摊情况下具有近似于线性的时间复杂度，约为字符串的长度加所有匹配的数量。然而由于需要找到所有匹配数，如果每个子串互相匹配（如字典为a，aa，aaa，aaaa，输入的字符串为aaaa），算法的时间复杂度会近似于匹配的二次函数。 该算法主要依靠构造一个有限状态机（类似于在一个trie树中添加失配指针）来实现。这些额外的失配指针允许在查找字符串失败时进行回退（例如设Trie树的单词cat匹配失败，但是在Trie树中存在另一个单词cart，失配指针就会指向前缀ca），转向某前缀的其他分支，免于重复匹配前缀，提高算法效率。 当一个字典串集合是已知的(例如一个计算机病毒库), 就可以以离线方式先将自动机求出并储存以供日后使用，在这种情况下，算法的时间复杂度为输入字符串长度和匹配数量之和。 UNIX系统中的一个命令fgrep就是以AC自动机算法作为基础实现的。 (zh)
- Алгоритм Ахо — Корасік — алгоритм пошуку рядків, створений Альфредом Ахо і . Алгоритм реалізує пошук множини підрядків із словника в цьому рядку. Час роботи пропорційно O (M + N + K), де N — довжина рядка-зразка, M — сумарна довжина рядків словника, а K — довжина відповіді, тобто сумарна довжина входжень слів із словника в рядок-зразок. Тому сумарний час роботи може бути квадратичним (наприклад, якщо в рядку «ааааааа», ми шукаємо слова «а», «аа», «ааа», …). (uk)
|
| rdfs:comment
|
- エイホ–コラシック法（英: Aho–Corasick algorithm）とは、1975年にアルフレッド・エイホと Margaret J. Corasick が発見した文字列探索アルゴリズムである。 (ja)
- 아호 코라식 알고리즘(Aho–Corasick string matching algorithm)은 Alfred V. Aho와 Margaret J. Corasick이 고안한 문자열 검색 알고리즘(매칭 알고리즘)이다. 패턴 1개를 탐색하는 매칭 알고리즘은 선형 시간에 구현됨을 KMP 등 여러 알고리즘을 통하여 증명되었다. 하지만 패턴 집합에 대하여 이러한 알고리즘을 수행하게 되면 패턴 개수에 비례하여 그 속도가 느려지게 된다. 즉, 의 시간 복잡도를 가지게 된다.(: 모든 패턴들의 길이 합, : 패턴 수, : text 크기) 하지만 Aho-Corasick 알고리즘을 이용하면 의 시간 복잡도로 패턴 집합에 대하여 패턴 길이와 텍스트의 선형 시간에 탐색을 처리할 수 있게 된다.(k: 텍스트 내에 패턴의 발생 수) 이러한 Aho-Corasick 알고리즘을 구현하기 위하여 Keyword Tree, Failure link, Output link 자료구조를 사용하여야 한다. (ko)
- Алгоритм Ахо — Корасик — алгоритм поиска подстроки, разработанный Альфредом Ахо и в 1975 году, реализует поиск множества подстрок из словаря в данной строке. Широко применяется в системном программном обеспечении, например, используется в утилите поиска grep. (ru)
- 在计算机科学中，Aho–Corasick算法是由Alfred V. Aho和Margaret J.Corasick 发明的字符串搜索算法，用于在输入的一串字符串中匹配有限组“字典”中的子串。它与普通字符串匹配的不同点在于同时与所有字典串进行匹配。算法均摊情况下具有近似于线性的时间复杂度，约为字符串的长度加所有匹配的数量。然而由于需要找到所有匹配数，如果每个子串互相匹配（如字典为a，aa，aaa，aaaa，输入的字符串为aaaa），算法的时间复杂度会近似于匹配的二次函数。 该算法主要依靠构造一个有限状态机（类似于在一个trie树中添加失配指针）来实现。这些额外的失配指针允许在查找字符串失败时进行回退（例如设Trie树的单词cat匹配失败，但是在Trie树中存在另一个单词cart，失配指针就会指向前缀ca），转向某前缀的其他分支，免于重复匹配前缀，提高算法效率。 当一个字典串集合是已知的(例如一个计算机病毒库), 就可以以离线方式先将自动机求出并储存以供日后使用，在这种情况下，算法的时间复杂度为输入字符串长度和匹配数量之和。 UNIX系统中的一个命令fgrep就是以AC自动机算法作为基础实现的。 (zh)
- Алгоритм Ахо — Корасік — алгоритм пошуку рядків, створений Альфредом Ахо і . Алгоритм реалізує пошук множини підрядків із словника в цьому рядку. Час роботи пропорційно O (M + N + K), де N — довжина рядка-зразка, M — сумарна довжина рядків словника, а K — довжина відповіді, тобто сумарна довжина входжень слів із словника в рядок-зразок. Тому сумарний час роботи може бути квадратичним (наприклад, якщо в рядку «ааааааа», ми шукаємо слова «а», «аа», «ааа», …). (uk)
- Algoritmus Aho-Corasick je vynalezený Alfredem Ahem a . Je to druh slovníkového vyhledávacího algoritmu, který ve vstupním textu hledá prvky konečné množiny řetězců. Vyhledává všechny prvky množiny najednou, jeho asymptotická složitost je proto lineární k délce všech vyhledávaných prvků plus délce vstupního textu plus délce výstupu. Jelikož algoritmus najde všechny výskyty, celkový počet výskytů pro celou množinu může být až kvadratický (například v případě, kdy vyhledávané řetězce jsou a, aa, aaa, aaaa a vstupní text je aaaa). (cs)
- In computer science, the Aho–Corasick algorithm is a string-searching algorithm invented by Alfred V. Aho and Margaret J. Corasick in 1975. It is a kind of dictionary-matching algorithm that locates elements of a finite set of strings (the "dictionary") within an input text. It matches all strings simultaneously. The complexity of the algorithm is linear in the length of the strings plus the length of the searched text plus the number of output matches. Note that because all matches are found, there can be a quadratic number of matches if every substring matches (e.g. dictionary = a, aa, aaa, aaaa and input string is aaaa). (en)
- Der Aho-Corasick-Algorithmus ist ein String-Matching-Algorithmus, der von Alfred V. Aho und 1975 entwickelt wurde. Der Algorithmus führt eine Art Wörterbuch-Vergleich durch, bei dem die Eingabe effizient nach vorher festgelegten Signaturen durchsucht wird. Dabei wird kein Zeichen der Eingabe mehr als einmal gelesen.Das Verfahren ist dann besonders effizient, wenn sich die Signaturen überlappen, d. h. in Präfix- und Suffix-Beziehungen stehen (z. B. {„Igel“, „Geld“, „Eldorado“}).Der Aho-Corasick-Algorithmus besteht aus zwei Phasen: (de)
- En Ciencias de la Computación, el Algoritmo de búsqueda de cadenas Aho–Corasick es un algoritmo de búsqueda de cadenas inventado por Alfred V. Aho y Margaret J. Corasick. Es un algoritmo que busca elementos (patrones) de un conjunto finito de cadenas (diccionario) dentro de un texto. Una de las ventajas que presenta es que procesa el texto de entrada solamente una vez, es decir, realiza la búsqueda de todos los patrones de forma simultánea. Si se considera el tamaño del alfabeto al cual pertenecen los patrones como constante, entonces la complejidad temporal del algoritmo es lineal en cuanto a la suma de las longitudes de los patrones más la longitud del texto. Si además se quieren conocer todas las ocurrencias de forma explícita, al orden del algoritmo hay que sumarle la cantidad de ocurr (es)
- L'algorithme d'Aho-Corasick est un algorithme de recherche de chaîne de caractères (ou motif) dans un texte dû à Alfred Aho et et publié en 1975. L'algorithme consiste à avancer dans une structure de données abstraite appelée dictionnaire qui contient le ou les mots recherchés en lisant les lettres du texte T une par une. La structure de données est implantée de manière efficace, ce qui garantit que chaque lettre du texte n'est lue qu'une seule fois. Généralement le dictionnaire est implanté à l'aide d'une trie ou arbre préfixe auquel on rajoute des liens suffixes. Une fois le dictionnaire implanté, l'algorithme a une complexité linéaire en la taille du texte T et des chaînes recherchées. (fr)
- Algorytm Aho-Corasick jest jednym z algorytmów wyszukiwania wzorca w tekście opracowanym przez Alfreda V. Aho oraz . Znajduje on w tekście wystąpienia słów ze słownika (pewnego zadanego zbioru wzorców). Wszystkie wzorce są szukane jednocześnie, co powoduje, że złożoność obliczeniowa algorytmu jest liniowa względem sumy długości wzorców, długości tekstu i liczby wystąpień wzorców w tekście. W tekście może jednak występować nawet kwadratowa od długości tekstu liczba wystąpień wzorców (np. gdy słownikiem jest a, aa, aaa, aaaa, zaś tekstem jest aaaa). Opis wyszukiwania wzorców w tekście abccab (pl)
- O algoritmo de Aho-Corasick é um algoritmo de pesquisa em strings inventado por Alfred V. Aho e , ambos pesquisadores do Bell Labs, em 1975. O objetivo do algoritmo é localizar todas as palavras chaves em textos, a partir de uma única interação, utilizando para tanto um dicionário contendo um conjunto finito de palavras chaves. A complexidade do algoritmo é linear (pt)
|
