| dbpedia-owl:abstract
| - In information theory and computer science, the Damerau–Levenshtein distance (named after Frederick J. Damerau and Vladimir I. Levenshtein) is a string metric for measuring the edit distance between two sequences. Informally, the Damerau–Levenshtein distance between two words is the minimum number of operations (consisting of insertions, deletions or substitutions of a single character, or transposition of two adjacent characters) required to change one word into the other. The Damerau–Levenshtein distance differs from the classical Levenshtein distance by including transpositions among its allowable operations in addition to the three classical single-character edit operations (insertions, deletions and substitutions). In his seminal paper, Damerau stated that in an investigation of spelling errors for an information-retrieval system, more than 80% were a result of a single error of one of the four types. Damerau's paper considered only misspellings that could be corrected with at most one edit operation. While the original motivation was to measure distance between human misspellings to improve applications such as spell checkers, Damerau–Levenshtein distance has also seen uses in biology to measure the variation between protein sequences.
- En la teoría de la información y en la ciencia de computadores, se llama distancia de Damerau-Levenshtein o distancia de edición al número mínimo de operaciones requeridas para transformar una cadena de caracteres en otra. Se entiende por operación, bien una inserción, eliminación, sustitución o transposición de dos caracteres. Lo que la distingue de la distancia de Levenshtein es que esta última cuenta como una sola operación de edición a cualquiera de las tres primeras, pero cuenta la transposición como dos operaciones de edición. Veamos un ejemplo sencillo, calculemos la distancia Damerau-Levenshtein entre la palabra DAR y la palabra DAS.Observamos que los dos primeros caracteres son iguales, y que simplemente hemos de transformar el tercer caracter, es decir, hemos de hacer una única transformación, que consistirá en sustituir la letra R por la letra S. Puesto que hemos hecho una transformación, la distancia Damerau-Levenshtein entre las palabras DAR y DAS es 1. Las distancia Damerau-Levenshtein se distingue de la distancia Damerau en que la primera considera que la operación de trasposición es una única operación. Un ejemplo de la operación de trasposición sería la que se daría entre las cadena de texto POTRO y PORTO. La distancia Damerau-Levenshtein entre estas dos palabras es 1 porque hemos hecho una operación para pasar de una a otra, la operación de trasposición. La distancia Damerau-Levenshtein se emplea, por ejemplo, en motores de búsqueda de cadenas de texto. Uno de los motores de búsqueda más conocidos que emplea esta distancia de edición es Lucene. Lo emplea, por ejemplo, para corregir errores de tecleo: imaginemos que estoy buscando las obras del director de cine "Hitchcock", y lo tecleo de forma incorrecta, tecleo "Hichcock". Este motor de búsqueda, y los motores de búsqueda que se basan en él tales como Solr, nos dan las coincidencias con la palabra tecleada con una distancia de hasta 2, de manera que, pese a tecleáramos mal el nombre del director, aparecerían los resultados correspondientes al nombre correcto del director, dado que entre "Hitchcock" y "Hichcock" la distancia es de 1. Hemos tomado como ejemplo varios casos sencillos, para cádenas de caracteres más largas y complejas se utiliza una matriz que se va completando de forma algorítmica de acuerdo a una serie de condiciones. Las condiciones lógicas para rellenar la matriz son las siguientes:
- ダメラウ・レーベンシュタイン距離（ダメラウ・レーベンシュタインきょり、英: Damerau–Levenshtein distance）は、2つの配列の間の編集距離を測定するために情報理論と計算機科学で使われる文字列計量である。2つの単語間のダメラウ・レーベンシュタイン距離は、一方の単語を他方の単語に変換するのに必要な最小の操作回数である。ここで1回の「操作」とは1文字の挿入、削除、置換、あるいは2つの隣り合う文字の交換である。ダメラウ・レーベンシュタイン距離はとウラジミール I. レーベンシュタインにちなんで名付けられた 。 古典的なレーベンシュタイン距離を定義する操作は3つの古典的単文字編集操作、すなわち文字の挿入、削除、および置換である。ダメラウ・レーベンシュタイン距離を定義する操作にはこれらに加えて隣接文字交換が含まれている 。 ダメラウによると、スペルミス全体の80%以上は、これら4操作のうちの1操作の誤り1つで表現できる。ダメラウの論文では、最大1回の編集操作で訂正できる綴り間違いのみが考慮されていた。当初の動機は、スペルチェッカなどのアプリケーション・ソフトウェアを改善するために人間のスペルミス間の距離を測定することであったが、ダメラウ・レーベンシュタイン距離は、生物学においてタンパク質配列の変異を測定するためにも使われている 。
- Расстояние Дамерау — Левенштейна (названо в честь учёных Фредерика Дамерау и Владимира Левенштейна) — это мера разницы двух строк символов, определяемая как минимальное количество операций вставки, удаления, замены и транспозиции (перестановки двух соседних символов), необходимых для перевода одной строки в другую. Является модификацией расстояния Левенштейна: к операциям вставки, удаления и замены символов, определённых в расстоянии Левенштейна добавлена операция транспозиции (перестановки) символов.
- En informatique théorique, la distance de Damerau–Levenshtein est une distance entre deux chaînes de caractères. On calcule le nombre minimum d'opérations nécessaires pour transformer une chaîne de caractères en une autre, où une opération est définie comme l'insertion, la suppression ou la substitution d'un simple caractère, ou comme une transposition de deux caractères adjacents. (en) a non seulement distingué ces quatre opérations d'édition, mais a aussi écrit qu'elles correspondent à plus de 80 % des fautes d'orthographe humaines. La distance d'édition a été introduite par Vladimir Levenshtein, qui a ensuite généralisé ce concept avec des opérations multiples d'édition, mais sans y inclure les transpositions. La motivation originale était de mesurer la distance entre un mot correct et un mot comportant une faute d'orthographe humaine afin d'améliorer des applications telles que les vérificateurs d'orthographe. Mais la distance Damerau-Levenshtein peut aussi être utilisée en biologie pour mesurer les variations entre des séquences d'ADN.
- Odległość Damerau-Levenshteina – miara odmienności napisów (skończonych ciągów znaków), zaproponowana przez F.J.Damerau. Stanowi uogólnienie odległości Levenshteina. Różnicą jest uznanie za działanie proste zamiany miejscami dwu sąsiednich znaków.
|
| comment
| - En informatique théorique, la distance de Damerau–Levenshtein est une distance entre deux chaînes de caractères. On calcule le nombre minimum d'opérations nécessaires pour transformer une chaîne de caractères en une autre, où une opération est définie comme l'insertion, la suppression ou la substitution d'un simple caractère, ou comme une transposition de deux caractères adjacents.
- En la teoría de la información y en la ciencia de computadores, se llama distancia de Damerau-Levenshtein o distancia de edición al número mínimo de operaciones requeridas para transformar una cadena de caracteres en otra. Se entiende por operación, bien una inserción, eliminación, sustitución o transposición de dos caracteres. Lo que la distingue de la distancia de Levenshtein es que esta última cuenta como una sola operación de edición a cualquiera de las tres primeras, pero cuenta la transposición como dos operaciones de edición.
- ダメラウ・レーベンシュタイン距離（ダメラウ・レーベンシュタインきょり、英: Damerau–Levenshtein distance）は、2つの配列の間の編集距離を測定するために情報理論と計算機科学で使われる文字列計量である。2つの単語間のダメラウ・レーベンシュタイン距離は、一方の単語を他方の単語に変換するのに必要な最小の操作回数である。ここで1回の「操作」とは1文字の挿入、削除、置換、あるいは2つの隣り合う文字の交換である。ダメラウ・レーベンシュタイン距離はとウラジミール I. レーベンシュタインにちなんで名付けられた 。 古典的なレーベンシュタイン距離を定義する操作は3つの古典的単文字編集操作、すなわち文字の挿入、削除、および置換である。ダメラウ・レーベンシュタイン距離を定義する操作にはこれらに加えて隣接文字交換が含まれている 。 ダメラウによると、スペルミス全体の80%以上は、これら4操作のうちの1操作の誤り1つで表現できる。ダメラウの論文では、最大1回の編集操作で訂正できる綴り間違いのみが考慮されていた。当初の動機は、スペルチェッカなどのアプリケーション・ソフトウェアを改善するために人間のスペルミス間の距離を測定することであったが、ダメラウ・レーベンシュタイン距離は、生物学においてタンパク質配列の変異を測定するためにも使われている 。
- In information theory and computer science, the Damerau–Levenshtein distance (named after Frederick J. Damerau and Vladimir I. Levenshtein) is a string metric for measuring the edit distance between two sequences. Informally, the Damerau–Levenshtein distance between two words is the minimum number of operations (consisting of insertions, deletions or substitutions of a single character, or transposition of two adjacent characters) required to change one word into the other.
- Расстояние Дамерау — Левенштейна (названо в честь учёных Фредерика Дамерау и Владимира Левенштейна) — это мера разницы двух строк символов, определяемая как минимальное количество операций вставки, удаления, замены и транспозиции (перестановки двух соседних символов), необходимых для перевода одной строки в другую. Является модификацией расстояния Левенштейна: к операциям вставки, удаления и замены символов, определённых в расстоянии Левенштейна добавлена операция транспозиции (перестановки) символов.
- Odległość Damerau-Levenshteina – miara odmienności napisów (skończonych ciągów znaków), zaproponowana przez F.J.Damerau. Stanowi uogólnienie odległości Levenshteina. Różnicą jest uznanie za działanie proste zamiany miejscami dwu sąsiednich znaków.
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
