| dbo:abstract |
L'algorithme de Wagner-Fischer est un algorithme de calcul de distance d'édition entre deux chaînes de caractères. Le calcul est général, il suffit de se donner une distance entre caractères. On peut donc l'appliquer au cas particulier de la distance de Levenshtein. La distance d'édition entre deux chaînes de caractères est le nombre minimal d'opérations d'edition élémentaires nécessaires pour transformer la première chaîne en la seconde (ou vice versa, par symétrie de la distance). Dans le cas de la distance de Levenshtein, les opérations d'édition élémentaires sont au nombre de trois : insertion, suppression ou substitution d'un caractère, et chacune a un coût de 1. On peut aussi appliquer l'algorithme de Wagner et Fischer au cas de deux opérations seulement : insertion et suppression. Dans ce cas, la substitution est équivalente à une suppression suivie d'une insertion et a un coût de 1 + 1 = 2. (fr) In computer science, the Wagner–Fischer algorithm is a dynamic programming algorithm that computes the edit distance between two strings of characters. (en) |
| dbo:wikiPageID |
29320010 (xsd:integer) |
| dbo:wikiPageLength |
9866 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID |
1117965265 (xsd:integer) |
| dbo:wikiPageWikiLink |
dbr:Prefix_(computer_science) dbr:David_Sankoff dbr:Invariant_(mathematics) dbr:Reductio_ad_absurdum dbr:Levenshtein_distance dbr:Matrix_(mathematics) dbc:String_metrics dbr:Computer_science dbr:Parallel_computing dbr:Data_dependency dbr:Lazy_evaluation dbr:Dynamic_programming dbr:Flood_fill dbr:Michael_J._Fischer dbr:Taras_Vintsiuk dbr:Big_O_notation dbr:Edit_distance dbr:Needleman–Wunsch_algorithm dbc:Algorithms_on_strings dbr:Pseudocode dbr:Fuzzy_string_searching dbr:Multiple_invention |
| dbp:wikiPageUsesTemplate |
dbt:Reflist dbt:Rp dbt:Tooltip dbt:Strings |
| dct:subject |
dbc:String_metrics dbc:Algorithms_on_strings |
| gold:hypernym |
dbr:Algorithm |
| rdf:type |
dbo:Software 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:WikicatAlgorithmsOnStrings |
| rdfs:comment |
In computer science, the Wagner–Fischer algorithm is a dynamic programming algorithm that computes the edit distance between two strings of characters. (en) L'algorithme de Wagner-Fischer est un algorithme de calcul de distance d'édition entre deux chaînes de caractères. Le calcul est général, il suffit de se donner une distance entre caractères. On peut donc l'appliquer au cas particulier de la distance de Levenshtein. La distance d'édition entre deux chaînes de caractères est le nombre minimal d'opérations d'edition élémentaires nécessaires pour transformer la première chaîne en la seconde (ou vice versa, par symétrie de la distance). (fr) |
| rdfs:label |
Algorithme de Wagner-Fischer (fr) Wagner–Fischer algorithm (en) |
| owl:sameAs |
freebase:Wagner–Fischer algorithm wikidata:Wagner–Fischer algorithm dbpedia-fa:Wagner–Fischer algorithm dbpedia-fr:Wagner–Fischer algorithm dbpedia-sr:Wagner–Fischer algorithm https://global.dbpedia.org/id/2dnbW |
| prov:wasDerivedFrom |
wikipedia-en:Wagner–Fischer_algorithm?oldid=1117965265&ns=0 |
| foaf:isPrimaryTopicOf |
wikipedia-en:Wagner–Fischer_algorithm |
| is dbo:wikiPageRedirects of |
dbr:Wagner-Fischer_edit_distance dbr:Wagner-Fischer_algorithm dbr:Wagner-Fisher_algorithm dbr:Wagner–Fischer_edit_distance dbr:Wagner–Fisher_algorithm |
| is dbo:wikiPageWikiLink of |
dbr:Dynamic_time_warping dbr:List_of_multiple_discoveries dbr:Viterbi_algorithm dbr:Wagner-Fischer_edit_distance dbr:Damerau–Levenshtein_distance dbr:Hunt–Szymanski_algorithm dbr:Edit_distance dbr:Needleman–Wunsch_algorithm dbr:Wagner-Fischer_algorithm dbr:Wagner-Fisher_algorithm dbr:Wagner–Fischer_edit_distance dbr:Wagner–Fisher_algorithm |
| is foaf:primaryTopic of |
wikipedia-en:Wagner–Fischer_algorithm |