Edit distance (original) (raw)

About DBpedia

編輯距離是針對二個字符串（例如英文字）的差異程度的量化量測，量測方式是看至少需要多少次的處理才能將一個字符串變成另一個字符串。編輯距離可以用在自然语言处理中，例如拼寫檢查可以根據一個拼錯的字和其他正確的字的編輯距離，判斷哪一個（或哪幾個）是比較可能的字。DNA也可以視為用A、C、G和T組成的字符串，因此編輯距離也用在生物信息学中，判斷二個DNA的類似程度。Unix 下的 diff 及 patch 即是利用编辑距离来进行文本编辑对比的例子。 編輯距離有幾種不同的定義，差異在可以對字符串進行的處理。 * 在萊文斯坦距離中，可以刪除、加入、取代字符串中的任何一個字元，也是較常用的編輯距離定義，常常提到編輯距離時，指的就是萊文斯坦距離。 * 也存在其他編輯距離的定義方式，例如 Damerau-Levenshtein 距离是一种莱文斯坦距离的变种，但允许以单一操作交换相邻的两个字符（称为字符转置），如 AB→BA 的距离是 1（交换）而非 2（先删除再插入、或者两次替换）。 * LCS（最长公共子序列）距離只允許刪除、加入字元。 * Jaro 距离只允许字符转置。 * 汉明距离只允許取代字元。

Property Value
dbo:abstract In computational linguistics and computer science, edit distance is a string metric, i.e. a way of quantifying how dissimilar two strings (e.g., words) are to one another, that is measured by counting the minimum number of operations required to transform one string into the other. Edit distances find applications in natural language processing, where automatic spelling correction can determine candidate corrections for a misspelled word by selecting words from a dictionary that have a low distance to the word in question. In bioinformatics, it can be used to quantify the similarity of DNA sequences, which can be viewed as strings of the letters A, C, G and T. Different definitions of an edit distance use different sets of string operations. Levenshtein distance operations are the removal, insertion, or substitution of a character in the string. Being the most common metric, the term Levenshtein distance is often used interchangeably with edit distance. (en) En informatique théorique, en biochimie et aussi dans des applications, en vision par ordinateur par exemple, la distance d'édition d'arbres (en anglais tree edit distance) est une mesure qui évalue, en termes de nombre de transformations élémentaires, le nombre d'opérations nécessaires et leur coût pour passer d'un arbre à un autre. C'est une notion qui étend, aux arbres, la distance d'édition (ou distance de Levenshtein) entre chaînes de caractères. Le distance aide à comparer par exemple la structure secondaire de l'ARN, ou des arbres phylogénétiques en biologie ou même pour guider les recommandations d'éditions aux étudiants dans des systèmes de tutorats intelligents. Plusieurs variantes de cette notion existent, en fonction de la nature des arbres que l'on considère. En toute généralité, ce sont des arbres abstraits ; de façon plus restrictive, on considère des arbres plans, c'est-à-dire tels que les sommets voisins d'un sommet sont ordonnés. Plus particulier encore est le cas des arbres plans enracinés : un tel arbre est composé d'une racine et d'une suite ordonnée de sous-arbres. C'est ce cas qui est détaillé ci-dessous. Un exposé de synthèse est donné par un article de Benjamin Paaßen. Les opérations élémentaires de transformations d'arbres sont, comme pour les chaînes de caractères, la suppression, l'insertion et le renommage, appliqués à un nœud d'un arbre. (fr) 編輯距離是針對二個字符串（例如英文字）的差異程度的量化量測，量測方式是看至少需要多少次的處理才能將一個字符串變成另一個字符串。編輯距離可以用在自然语言处理中，例如拼寫檢查可以根據一個拼錯的字和其他正確的字的編輯距離，判斷哪一個（或哪幾個）是比較可能的字。DNA也可以視為用A、C、G和T組成的字符串，因此編輯距離也用在生物信息学中，判斷二個DNA的類似程度。Unix 下的 diff 及 patch 即是利用编辑距离来进行文本编辑对比的例子。 編輯距離有幾種不同的定義，差異在可以對字符串進行的處理。 * 在萊文斯坦距離中，可以刪除、加入、取代字符串中的任何一個字元，也是較常用的編輯距離定義，常常提到編輯距離時，指的就是萊文斯坦距離。 * 也存在其他編輯距離的定義方式，例如 Damerau-Levenshtein 距离是一种莱文斯坦距离的变种，但允许以单一操作交换相邻的两个字符（称为字符转置），如 AB→BA 的距离是 1（交换）而非 2（先删除再插入、或者两次替换）。 * LCS（最长公共子序列）距離只允許刪除、加入字元。 * Jaro 距离只允许字符转置。 * 汉明距离只允許取代字元。 (zh)
dbo:wikiPageExternalLink https://dblp.org/pers/hd/s/Schmidt:Jeanette_P=
dbo:wikiPageID 406427 (xsd:integer)
dbo:wikiPageLength 18548 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID 1099296255 (xsd:integer)
dbo:wikiPageWikiLink dbr:Natural_language_processing dbr:Approximate_string_matching dbr:DNA dbr:Sequence_alignment dbr:Levenshtein_automaton dbr:Levenshtein_distance dbr:Optical_character_recognition dbr:Gad_Landau dbr:Context-free_language dbc:String_metrics dbr:String_metric dbr:Computational_biology dbr:Computational_linguistics dbr:Computer_science dbr:Byte dbr:Time_Warp_Edit_Distance dbr:Time_complexity dbr:ASCII dbr:Aho–Corasick_string_matching_algorithm dbr:Damerau–Levenshtein_distance dbr:Dynamic_programming dbr:Esko_Ukkonen dbr:Eugene_Myers dbr:Formal_language dbr:Graph_edit_distance dbr:Hirschberg's_algorithm dbr:Recursive_definition dbr:Hamming_distance dbr:Jaro–Winkler_distance dbr:Bioinformatics dbr:Bitap_algorithm dbr:Transposition_(mathematics) dbr:Frederick_J._Damerau dbr:Metric_space dbr:Recursion_(computer_science) dbr:Longest_common_subsequence_problem dbr:Smith–Waterman_algorithm dbr:Exponential_time dbr:Metric_(mathematics) dbr:String-to-string_correction_problem dbr:Regular_grammar dbr:Wagner–Fischer_algorithm dbr:Spell_checker dbr:Space_complexity dbr:Jaro_distance dbr:Deterministic_finite_state_automaton dbr:Longest_common_subsequence dbr:String_(computing)
dbp:wikiPageUsesTemplate dbt:Main dbt:Math dbt:Mvar dbt:Reflist dbt:Rp dbt:Short_description dbt:Sup dbt:Strings
dct:subject dbc:String_metrics
gold:hypernym dbr:Way
rdf:type yago:WikicatStringSimilarityMeasures yago:Abstraction100002137 yago:Act100030358 yago:Action100037396 yago:Activity100407535 yago:Algorithm105847438 yago:Choice100161243 yago:Decision100162632 yago:Event100029378 yago:Maneuver100168237 yago:Measure100174412 yago:Move100165942 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:WikicatAlgorithms yago:WikicatAlgorithmsOnStrings
rdfs:comment 編輯距離是針對二個字符串（例如英文字）的差異程度的量化量測，量測方式是看至少需要多少次的處理才能將一個字符串變成另一個字符串。編輯距離可以用在自然语言处理中，例如拼寫檢查可以根據一個拼錯的字和其他正確的字的編輯距離，判斷哪一個（或哪幾個）是比較可能的字。DNA也可以視為用A、C、G和T組成的字符串，因此編輯距離也用在生物信息学中，判斷二個DNA的類似程度。Unix 下的 diff 及 patch 即是利用编辑距离来进行文本编辑对比的例子。 編輯距離有幾種不同的定義，差異在可以對字符串進行的處理。 * 在萊文斯坦距離中，可以刪除、加入、取代字符串中的任何一個字元，也是較常用的編輯距離定義，常常提到編輯距離時，指的就是萊文斯坦距離。 * 也存在其他編輯距離的定義方式，例如 Damerau-Levenshtein 距离是一种莱文斯坦距离的变种，但允许以单一操作交换相邻的两个字符（称为字符转置），如 AB→BA 的距离是 1（交换）而非 2（先删除再插入、或者两次替换）。 * LCS（最长公共子序列）距離只允許刪除、加入字元。 * Jaro 距离只允许字符转置。 * 汉明距离只允許取代字元。 (zh) In computational linguistics and computer science, edit distance is a string metric, i.e. a way of quantifying how dissimilar two strings (e.g., words) are to one another, that is measured by counting the minimum number of operations required to transform one string into the other. Edit distances find applications in natural language processing, where automatic spelling correction can determine candidate corrections for a misspelled word by selecting words from a dictionary that have a low distance to the word in question. In bioinformatics, it can be used to quantify the similarity of DNA sequences, which can be viewed as strings of the letters A, C, G and T. (en) En informatique théorique, en biochimie et aussi dans des applications, en vision par ordinateur par exemple, la distance d'édition d'arbres (en anglais tree edit distance) est une mesure qui évalue, en termes de nombre de transformations élémentaires, le nombre d'opérations nécessaires et leur coût pour passer d'un arbre à un autre. C'est une notion qui étend, aux arbres, la distance d'édition (ou distance de Levenshtein) entre chaînes de caractères. Le distance aide à comparer par exemple la structure secondaire de l'ARN, ou des arbres phylogénétiques en biologie ou même pour guider les recommandations d'éditions aux étudiants dans des systèmes de tutorats intelligents. (fr)
rdfs:label Distance d'édition sur les arbres (fr) Edit distance (en) 編輯距離 (zh)
owl:sameAs freebase:Edit distance yago-res:Edit distance wikidata:Edit distance dbpedia-fr:Edit distance dbpedia-zh:Edit distance https://global.dbpedia.org/id/4ijcH
prov:wasDerivedFrom wikipedia-en:Edit_distance?oldid=1099296255&ns=0
foaf:isPrimaryTopicOf wikipedia-en:Edit_distance
is dbo:wikiPageRedirects of dbr:Applications_of_edit_distance dbr:Levehstein_distance dbr:Levenshtein_algorithm dbr:Levenshtein_string_distance dbr:Optimal_string_alignment dbr:String_edit_distance
is dbo:wikiPageWikiLink of dbr:Method_of_Four_Russians dbr:Time_series dbr:Barna_Saha dbr:Approximate_string_matching dbr:DNA_encryption dbr:Double_Cut_and_Join_Model dbr:Sequence_alignment dbr:Levenshtein_distance dbr:Error-tolerant_design dbr:Fuzzy_extractor dbr:Gad_Landau dbr:String_metric dbr:Applications_of_edit_distance dbr:Deniable_encryption dbr:Full-text_search dbr:Stack-sortable_permutation dbr:Data_synchronization dbr:Distance dbr:Gap_penalty dbr:Heavy_path_decomposition dbr:Jewels_of_Stringology dbr:Spelling_suggestion dbr:Damerau–Levenshtein_distance dbr:Dynamic_programming dbr:File_comparison dbr:Chvátal–Sankoff_constants dbr:Graph_edit_distance dbr:Word_error_rate dbr:Proximity_search_(text) dbr:Rebus dbr:Speech_recognition dbr:Hamming_distance dbr:Jaro–Winkler_distance dbr:Diff dbr:Fibonacci_coding dbr:Kristin_Lauter dbr:Metric_space dbr:Secure_multi-party_computation dbr:Longest_common_subsequence_problem dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:List_of_unsolved_problems_in_computer_science dbr:String-to-string_correction_problem dbr:Tree_alignment dbr:Wagner–Fischer_algorithm dbr:Property_testing dbr:Levehstein_distance dbr:Levenshtein_algorithm dbr:Levenshtein_string_distance dbr:Optimal_string_alignment dbr:String_edit_distance
is foaf:primaryTopic of wikipedia-en:Edit_distance