Chociaż istnieje wiele pytań edycji odległości, takich jak to , nie ma prostego pytania, aby napisać program, który oblicza odległość Levenshteina.
Jakaś ekspozycja
Odległość edycji Levenshteina między dwoma łańcuchami to minimalna możliwa liczba wstawek, usunięć lub podstawień w celu konwersji jednego słowa na inne. W takim przypadku każde wstawienie, usunięcie i zastąpienie kosztuje 1.
Na przykład odległość między roll
i rolling
wynosi 3, ponieważ usunięcie kosztuje 1, a my musimy usunąć 3 znaki. Odległość między toll
i tall
wynosi 1, ponieważ zamiana kosztuje 1.
Zasady
- Dane wejściowe będą miały dwa ciągi. Możesz założyć, że łańcuchy są małe, zawierają tylko litery, nie są puste i mają maksymalnie 100 znaków.
- Wyjście będzie minimalną odległością edycyjną Levenshteina dwóch łańcuchów, jak zdefiniowano powyżej.
- Twój kod musi być programem lub funkcją. Nie musi to być funkcja nazwana, ale nie może to być funkcja wbudowana, która bezpośrednio oblicza odległość Levenshteina. Inne wbudowane są dozwolone.
- To jest golf golfowy, więc wygrywa najkrótsza odpowiedź.
Kilka przykładów
>>> lev("atoll", "bowl")
3
>>> lev("tar", "tarp")
1
>>> lev("turing", "tarpit")
4
>>> lev("antidisestablishmentarianism", "bulb")
27
Jak zawsze, jeśli problem jest niejasny, daj mi znać. Powodzenia i dobrej gry w golfa!
Katalog
var QUESTION_ID=67474;var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";var COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk";var OVERRIDE_USER=47581;var answers=[],answers_hash,answer_ids,answer_page=1,more_answers=true,comment_page;function answersUrl(index){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+index+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(index,answers){return"http://api.stackexchange.com/2.2/answers/"+answers.join(';')+"/comments?page="+index+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:true,success:function(data){answers.push.apply(answers,data.items);answers_hash=[];answer_ids=[];data.items.forEach(function(a){a.comments=[];var id=+a.share_link.match(/\d+/);answer_ids.push(id);answers_hash[id]=a});if(!data.has_more)more_answers=false;comment_page=1;getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:true,success:function(data){data.items.forEach(function(c){if(c.owner.user_id===OVERRIDE_USER)answers_hash[c.post_id].comments.push(c)});if(data.has_more)getComments();else if(more_answers)getAnswers();else process()}})}getAnswers();var SCORE_REG=/<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;var OVERRIDE_REG=/^Override\s*header:\s*/i;function getAuthorName(a){return a.owner.display_name}function process(){var valid=[];answers.forEach(function(a){var body=a.body;a.comments.forEach(function(c){if(OVERRIDE_REG.test(c.body))body='<h1>'+c.body.replace(OVERRIDE_REG,'')+'</h1>'});var match=body.match(SCORE_REG);if(match)valid.push({user:getAuthorName(a),size:+match[2],language:match[1],link:a.share_link,});else console.log(body)});valid.sort(function(a,b){var aB=a.size,bB=b.size;return aB-bB});var languages={};var place=1;var lastSize=null;var lastPlace=1;valid.forEach(function(a){if(a.size!=lastSize)lastPlace=place;lastSize=a.size;++place;var answer=jQuery("#answer-template").html();answer=answer.replace("{{PLACE}}",lastPlace+".").replace("{{NAME}}",a.user).replace("{{LANGUAGE}}",a.language).replace("{{SIZE}}",a.size).replace("{{LINK}}",a.link);answer=jQuery(answer);jQuery("#answers").append(answer);var lang=a.language;lang=jQuery('<a>'+lang+'</a>').text();languages[lang]=languages[lang]||{lang:a.language,lang_raw:lang.toLowerCase(),user:a.user,size:a.size,link:a.link}});var langs=[];for(var lang in languages)if(languages.hasOwnProperty(lang))langs.push(languages[lang]);langs.sort(function(a,b){if(a.lang_raw>b.lang_raw)return 1;if(a.lang_raw<b.lang_raw)return-1;return 0});for(var i=0;i<langs.length;++i){var language=jQuery("#language-template").html();var lang=langs[i];language=language.replace("{{LANGUAGE}}",lang.lang).replace("{{NAME}}",lang.user).replace("{{SIZE}}",lang.size).replace("{{LINK}}",lang.link);language=jQuery(language);jQuery("#languages").append(language)}}
body{text-align:left!important}#answer-list{padding:10px;width:290px;float:left}#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="language-list"> <h2>Shortest Solution by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr> </thead> <tbody id="languages"> </tbody> </table> </div> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr> </thead> <tbody id="answers"> </tbody> </table> </div> <table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table>
Matlab,
177163 bajtówJest to prosta implementacja tej formuły:
Nie golfowany:
źródło
Python 2,
151140138 bajtówPowolna rekurencyjna implementacja odległości Levenshtein na podstawie Wikipedii (dzięki @Kenney za golenie 11 znaków i @ Sherlock9 za kolejne 2).
Podanie poprawnych odpowiedzi dla przedstawionych przypadków testowych:
źródło
if !n*m:return n if n else m
, a kolejne dwa przezreturn 1+min([ f(..), f(..), f(..) - (s[..] == t[..]) ])
.f(m-1,n-1)-(s[m-1]==t[n-1])
zamiastf(m-1,n-1)+(s[m-1]!=t[n-1])-1
.JavaScript (ES6) 106
113 122Edytuj 16 bajtów zapisanych zgodnie z sugestiami @Neil
Jako funkcja anonimowa.
Jest to golfowa implementacja algorytmu Wagnera-Fischera dokładnie taka, jak opisano w powiązanym artykule na Wikipedii, w sekcji Iteracyjna z dwoma wierszami macierzy (nawet jeśli w rzeczywistości używany jest tylko 1 wiersz - tablica w )
Mniej golfa
Testowy fragment kodu
źródło
[...[0,...t].keys()]
zamiast tego? Zapisuje 2 bajty, jeśli możesz.[...[,...t].keys()]
myślę, że też działa.[...s].map()
:(s,t)=>(w=[...[,...t].keys()],[...s].map((u,i)=>w=w.map((v,j)=>p=j--?Math.min(p,v,w[j]-(s[i-1]==t[j]))+1:i)),p)
Python 2, 118 bajtów
Golf tego rozwiązania , ale nie wygląda na to, że Willem był aktywny od roku, więc muszę go opublikować:
Spróbuj na repl.it
Pobiera dwa ciągi i podaje odległość do
STDOUT
( dozwoloną przez meta ). Proszę skomentować sugestie, jestem pewien, że można to jeszcze pograć w golfa.źródło
input()
s lub aninput().split()
?s
it
gdzieś w kodzie. Nieważne. Dobra robota: Dm or n
. Możesz go zastąpićm+n
.AutoIt , 333 bajty
Przykładowy kod testowy:
daje
źródło
k4, 66 bajtów
Nudny i w zasadzie nie golfisty implant algo. Dawny.:
źródło
Poważnie,
868278 bajtówHex Dump:
Wypróbuj online
(Pamiętaj, że link prowadzi do innej wersji, ponieważ coś w tłumaczeniu online jest zepsute z nową, krótszą wersją, mimo że działa dobrze z tłumaczem do pobrania).
Chodzi o najprostszą implementację. Poważnie pozwala na definicję rekurencyjną. Jest bardzo powolny, ponieważ w ogóle nie zapamiętuje. Być może metoda tabelaryczna może być krótsza (być może przy użyciu rejestrów jako wierszy), ale jestem z tego całkiem zadowolony, pomimo tego, jak wiele zawiera niedociągnięć w mowie. Tego można użyć
jako prawidłowe wywołanie funkcji dwuparlamentarnej było całkiem miłym znaleziskiem.
Wyjaśnienie:
źródło
Python 3,
267216184162 bajtówTa funkcja oblicza odległość Levenshteina przy użyciu odpowiedniej wielkości tablicy
2 x len(word_2)+1
.Edycja: Nie zbliża się to do odpowiedzi Willem's Python 2, ale tutaj jest bardziej golfowa odpowiedź z wieloma drobnymi udoskonaleniami tu i tam.
Nie golfowany:
źródło
Retina ,
7872 bajtówWypróbuj online!
W pewnym sensie jest to czyste rozwiązanie wyrażenia regularnego, w którym wynikiem jest liczba pozycji, z którymi pasuje wyrażenie regularne. Bo czemu nie...
Uczciwe ostrzeżenie, jest to bardzo nieefektywne. Działa to w ten sposób, że odciąża rzeczywistą optymalizację do backtrackera silnika regex, który po prostu brutalnie wymusza wszystkie możliwe wyrównania, zaczynając od jak najmniejszej liczby zmian i pozwalając na jeszcze jedną, aż możliwe będzie dopasowanie ciągów z dodatkami, usunięciami i podstawieniami .
W przypadku nieco bardziej sensownego rozwiązania, ten dopasowuje tylko raz i nie ma żadnych negatywnych spojrzeń. Tutaj wynikiem jest liczba przechwyceń w grupie
2
, do których można uzyskać dostępmatch.Groups[2].Captures.Count
na przykład w języku C #. Jest to jednak nadal okropnie nieefektywne.Wyjaśnienie
Wyjaśniam drugą wersję powyżej, ponieważ jest ona koncepcyjnie nieco łatwiejsza (ponieważ jest to tylko jedno dopasowanie wyrażenia regularnego). Oto wersja bez golfisty Nazwałam grupy (lub uczyniłam je nie przechwytującymi) i dodałem komentarze. Pamiętaj, że komponenty w wyglądzie powinny być odczytywane od tyłu do przodu, ale alternatywy i spojrzenia wewnątrz nich powinny być odczytywane od przodu do tyłu. Tak.
Jedyną różnicą w stosunku do 72-bajtowej wersji jest to, że możemy porzucić pozycję wiodącą
.+
(i drugą grupę na początku), znajdując pozycje na końcu, gdzie nie mamy wystarczającej<ops>
liczby, i zliczamy wszystkie te pozycje.źródło
Haskell ,
6764 bajtówWypróbuj online! Przykładowe użycie:
"turing" # "tarpit"
daje4
.Objaśnienie (dla poprzedniej 67-bajtowej wersji)
To jest rozwiązanie rekurencyjne. Biorąc pod uwagę dwa ciągi
e
if
, najpierw porównujemy ich pierwsze znakia
ib
. Jeśli są one równe, to odległość Levenshteinae
if
jest taka sama jak odległość Levenshteinar
is
, pozostała częśće
if
po usunięciu pierwszych znaków. W przeciwnym razie alboa
albob
musi zostać usunięty, albo jeden jest zastąpiony drugim.[r#f,e#s,r#s]
rekurencyjnie oblicza Levenshtein dla tych trzech przypadków,minimum
wybiera najmniejszą i1
dodaje, aby uwzględnić niezbędną operację usunięcia lub zastąpienia.Jeśli jeden z łańcuchów jest pusty, my i na drugim wierszu. W tym przypadku odległość jest tylko długością niepustego łańcucha lub równoważnie długością obu łańcuchów połączonych razem.
źródło
Python 3 ,
1059493 bajty-11 bajtów przez xnor
Wersja najkrótsza implementacja na Wikibooks .
Wypróbuj online!
źródło
l=
uwzględnić i policzyć, ponieważ funkcja jest rekurencyjna. Możesz połączyć przypadki baz wif b>""<a else len(a+b)
.Haskell, 136 bajtów
Zadzwoń
e
. Trochę wolno naantidisestablishmentarianism
itp.źródło
Jolf, 4 bajty
Wypróbuj tutaj!
Dodałem to wbudowane wczoraj, ale widziałem to wyzwanie dzisiaj, czyli właśnie teraz. Mimo to ta odpowiedź nie jest konkurencyjna.
W nowszej wersji:
przyjmuje niejawne drugie wejście.
źródło
GNU Prolog, 133 bajty
Przyjmuje krotkę jako argument. Przykład użycia:
m
określa, żeB
jestA
albo bezpośrednio, albo z usuniętym pierwszym znakiem.d
zastosowaniam
jako podprogram do wyliczenia się odległość między elementami edycji krotka (czyli odległość serii edycji, który przekształca się w drugą). Wtedyl
to standardowy trik do znalezienia minimumd
(wziąć dowolną odległość, a następnie podjąć dowolny mniejszy dystans, powtórki, aż nie można się mniejszy).źródło
Perl,
168166163 bajtówImplementacja rekurencyjna. Zapisz w
file.pl
i uruchom jakoperl file.pl atoll bowl
.Pozostałe dwie implementacje są dłuższe (pełna matryca: 237 bajtów,
dwieiteracyjne jednorzędowe: 187).()
w dzwonieniul
.return
przez nadużywaniedo
w trynkuźródło
APL (Dyalog Classic) , 34 bajty
Wypróbuj online!
źródło
C, 192 bajty
Szczegółowy
źródło
C #,
215210198bardziej czytelny:
źródło
PowerShell v3 +, 247 bajtów
Skończyło się to na rozwiązaniu innych problemów związanych z LD.
Wyjaśnienie kodu z komentarzami.
źródło
JavaScript (ES6),
95 9189 bajtówPobiera dane wejściowe jako
(source)(target)
. Zasadniczo port odpowiedzi Pythona @ Willema (później zoptymalizowanej przez @FlipTack ).Wypróbuj online!
źródło