Znajdź minimalną odległość edycji między dwoma ciągami

13

Wyjaśnienie

Odległość edytować między dwóch ciągów jest funkcją minimalnej możliwej liczby insercji, delecji lub podstawienia do konwersji jednego słowa do słowa.

Wstawienia i usunięcia kosztują 1, a zamiany kosztują 2.

Na przykład odległość między ABi Awynosi 1, ponieważ usunięcie kosztuje 1, a jedyną potrzebną edycją jest usunięcie Bznaku.

Odległość między CARi FARwynosi 2, ponieważ podstawienia kosztują 2. Innym sposobem na to jest jedno usunięcie i jedno wstawienie.

Zasady

Biorąc pod uwagę dwa ciągi wejściowe (dostarczone jest jednak wygodne w twoim języku), twój program musi znaleźć minimalną odległość edycji między tymi dwoma ciągami.

Możesz założyć, że ciągi zawierają tylko znaki A-Zi mają mniej niż 100 znaków i więcej niż 0 znaków.

To jest golf golfowy , więc wygrywa najkrótsze rozwiązanie.

Przykładowe przypadki testowe

ISLANDER, SLANDER
> 1
MART, KARMA
> 5
KITTEN, SITTING
> 5
INTENTION, EXECUTION
> 8
Peter Olson
źródło
Zrobiłem to raz w Excelu w mojej klasie algorytmów. Fajnie było zamienić projekt jako dokument .xls. Właściwie to działało całkiem dobrze. Zobaczę, czy mogę to znaleźć.
captncraig
PHP powinno to łatwo wygrać.
st0le,
@ st0le - Wbudowana levenshteinfunkcja traktuje podstawienia jako jedną edycję (zastępowanie), a nie dwie (usuwanie + wstawianie).
Pan Llama,

Odpowiedzi:

7

pieprzenie mózgu, 2680

+>>>>>>>>>>>>>>>>>>>>>>++++++>,<[->-----<]>--[+++++++++++++++++++++
+++++++++++>>[->>+<<]>>+<<,--------------------------------]>>[-<<<
+>>>]<<<<[>[-<<+>>]<<<]>[-<<<<<+>>>>>]>[>>],----------[++++++++++>>
[->>+<<]>>+<<,----------]>>[-<<<+>>>]<<<<[>[-<<+>>]<<<]>[-<<+>>]<<[
-<+>>+<]<<<[->+<]>[-<+>>>>+<<<]>>>[-<+>]<[->+>+<<]<[-<+>]<[->+>+<<]
<[-<+>>+<]<[->+<]>>>>>>[-[->>+<<]<<[->>+<<]<<[->>+<<]>>>>>>]<<[->>+
>+<<<]>>>[-<<<+>>>]<[->>+[->+>+<<]<<[->>+<<]>>]>>[-]<[<<]<<<+[->>>+
<<<]>>>[-<+<<+>>>]<<<<<[->>[->>>>[->>+<<]<<[->>+<<]<<[->>+<<]<<[->>
+<<]>>>>]>>[->>>>+<<<<]>>>>[-<<<<+<<+>>>>>>]<<+[->>+<<]>>[-<<+<+>>>
]<<<<<<<<]>>[-]>>[-]>>[-]-[+<<-]+>>>>>>>>>>>>>>>>>[-<+>]<[->+<<<<+>
>>]<<<[->>>>>>[-<+>]<[->+<<<<+>>>]<<<<<<<[-]<<+>>>>>>[-<<<<+>>>>>>>
>>>[-<+>]<[->+>+<<]<<<<<<<<<[->+<]>[->>>>>>>>+<<<<<<<<<+>]<<<[->+<]
>[->>>>>>>>+<<<<<<<<<+>]>>>>>>>>>[-<<<<<+>>>>>]<<<<<[->>+>>>+<<<<<]
>>>>>>>>[-[->>+<<]<<[->>+<<]<<[->>+<<]<<[->>+<<]>>>>>>>>]<<<<<<+>>-
[-<<[-<<<<+>>>>]<<<<[->>+>>+<<<<]>>[->>>>>>[->>+<<]<<[->>+<<]<<[->>
+<<]<<[->>+<<]>>]>>>>]>>[->>+<<]>>[-<<+>>>>+<<]->>-[-[->>+<<]>>]>[-
>+<]>[-<+>>>+<<]<<<[->+<]>[-<+>>>+<<]+[->>[-<<+>>]>>[-<<+>>]<<<<<<+
]<<<<<<[->>>>>>+<<<<<<]>>>>>>>>[-<<<<<<<<+>>>>>>>>]<<<<[->>>>+<<<<]
-<<[-]>>>>>>>>[-<<<<<<<<+>>>>>>>>]<<<<[->>[->>+<<]<<[->>+<<]>>]>>-[
-[->>+<<]>>]<[->+<]>[-<+>>>+<<]+[->>[-<<+>>]<<<<+]>>[-<<+>>]<<<<<<<
<-[+>>[-<<+>>]>>[-<<+>>]>>[-<<+>>]<<<<<<<<-]+>>>[-]<[->+<]>>>[-]<[-
>+<]>>>[-]<[->+<]>>>[->+<]>[-<+>>>>>>>>>>>>>+<<<<<<<<<<<<]>>>>>>>>>
>>>-[-[->>+<<]>>]>[->+<]>[-<+<+>>]<<<<-[+>>[-<<+>>]<<<<-]+>>[-<+>]>
>>>>>>>>[->+<]>[-<+>>>>>>>>>>>+<<<<<<<<<<]>>>>>[->+<]>[-<+>>>>>+<<<
<]>>>>-[-[->>+<<]>>]>[->+<]>[-<+<+>>]<<<<-[+>>[-<<+>>]<<<<-]+>[->-<
]>[-<[-]+>]<[->>>+<<<]>>>[-<<+<+>>>]<<-[+>[->+<]<]<[->>+<-[[-]>[->+
<]>[-<+>>>+<<]+>>[-<<[-]>>]<[->+<]>[-<+>>>+<<]+>>[-<<[-]>>]<[->+<]>
[-<+>>>+<<]+>>[-<<[-]>>]<<[-<<[-]+>>]<<[-<<[-]+>>]<<[-<<[-]+>>]<<<+
>->->>->>-<<<<<]<[->+<]]>[-<+>]>>[-<<<+>>>]<<<[->>>>>>>>>>>>>+<<<<<
<<<<<<<<]>>>>>>>>[->+<]>[-<+>>>>>>>>>+<<<<<<<<]>[->+<]>[-<+>>>>>>>>
>+<<<<<<<<]>>>>>>>>>[->>>+<<<]>>>[-<<+<+>>>]<<<<<[->>>>>+<<<<<]>>>>
>[-<<<<<+<<<+>>>>>>>>]<<<<<<<<+>>>>>>[-[->>+<<]<<[->>+<<]<<[->>+<<]
<<[->>+<<]<<[->>+<<]>>>>>>>>>>]<<<<[-<<[-<<<<<<+>>>>>>]<<<<<<[->>+>
>>>+<<<<<<]>>[->>>>>>>>[->>+<<]<<[->>+<<]<<[->>+<<]<<[->>+<<]<<[->>
+<<]>>]>>>>>>]<<[-]<<[->>>>+<<<<]>>>>>>[-[->>+<<]<<[->>+<<]>>>>]<<[
->>>>>+<<<<<]-[+<<-]+>>>>>>>>>>>>>>>]<<]>>>>>>>>[->+<]<<[->+<]<<[->
+<]>>>>>[-[->>+<<]<<[->>+<<]<<[->>+<<]>>>>>>]<<<<[->>[->>>>+<<<<]>>
>>[-<<+<<+>>>>]<<+[-[->>+<<]<<[->>+<<]<<[->>+<<]>>>>>>]<<<<]>>[-[->
>+<<]>>]>>>>++++++++++<[->-[>+>>]>[+[-<+>]>+>>]<<<<<]>>>[->-[>+>>]>
[+[-<+>]>+>>]<<<<<]>[-]<++++++[->++++++++[->+>+<<<<+>>]<]>>>.<.<<<.

Oczywiście przy użyciu programowania dynamicznego.

Ciągi wejściowe powinny być oddzielone spacją, a następnie nowy wiersz. Na przykład:

INTENTION EXECUTION
008
pudełko kartonowe
źródło
1
Starannie dopasowane i bardzo czytelne - podoba mi się, +1!
Thomas
Czy to jest język komputerowy? : O
To najbardziej mylące poddanie się temu pytaniu ... +1 tylko dlatego, że to BF.
HyperNeutrino
5

Python, 138 148 152 znaków

Ok, znałem tę zasadę, ale nigdy wcześniej nie wdrożyłem odległości edycji, więc oto:

x,y=raw_input().split()
d=range(99)
for a in x:
 c=d;d=[d[0]+1]
 for b,p,q in zip(y,c[1:],c):d+=[min(d[-1]+1,p+1,q+2*(a!=b))]
print d[-1]
Han
źródło
4

PHP, 40

Przestrzega zasad, jak podano, ale nie ducha zasad:

<?=levenshtein($argv[1],$argv[2],1,2,1);

Jako argument przyjmuje dwa parametry. Przykład numerem: php edit_dist.php word1 word2.
Zwykle levenshtein()uważa podstawienie za jedną operację, ale ma on postać przeciążoną, w której można określić wagi wstawiania / sub / usuwania. W tym przypadku jest to 1/2/1.

Pan Llama
źródło
3

APL (90 znaków)

⊃⌽({h←1+c←⊃⍵⋄d←h,1↓⍵⋄h,(⊂⍵){y←⍵+1⋄d[y]←⍺{h⌷b=⍵⌷a:⍵⌷⍺⋄1+d[⍵]⌊y⌷⍺}⍵}¨⍳x}⍣(⊃⍴b←,⍞))0,⍳x←⍴a←,⍞

Używam Dyalog APL jako mojego interpretera, z ⎕IOustawieniem na 1 i ⎕MLustawieniem na 0. Funkcja direct ( { ... }) oblicza, podając wiersz jako dane wejściowe, następny wiersz w macierzy odległości. (Rozpoczyna się od pierwszego wiersza:. 0,⍳x) Operator mocy ( ) służy do zagnieżdżenia funkcji raz dla każdego znaku w drugim ciągu ( ⊃⍴b). Po tym wszystkim ostatni wiersz jest odwracany ( ) i pobierany jest jego pierwszy element ( ).

Przykład:

      ⊃⌽({h←1+c←⊃⍵⋄d←h,1↓⍵⋄h,(⊂⍵){y←⍵+1⋄d[y]←⍺{h⌷b=⍵⌷a:⍵⌷⍺⋄1+d[⍵]⌊y⌷⍺}⍵}¨⍳x}⍣(⊃⍴b←,⍞))0,⍳x←⍴a←,⍞
LOCKSMITH
BLACKSMITH
3
      ⊃⌽({h←1+c←⊃⍵⋄d←h,1↓⍵⋄h,(⊂⍵){y←⍵+1⋄d[y]←⍺{h⌷b=⍵⌷a:⍵⌷⍺⋄1+d[⍵]⌊y⌷⍺}⍵}¨⍳x}⍣(⊃⍴b←,⍞))0,⍳x←⍴a←,⍞
GATTTGTGACGCACCCTCAGAACTGCAGTAATGGTCCAGCTGCTTCACAGGCAACTGGTAACCACCTCATTTGGGGATGTTTCTGCCTTGCTAGCAGTGCCAGAGAGAACTTCATCATTGTCACCTCATCAAAGACTACTTTTTCAGACATCTCCTGTAG
AAGTACTGAACTCCTAATATCACCAATTCTTCTAAGTTCCTGGACATTGATCCGGAGGAGGATTCGCAGTTCAACATCAAGGTAAGGAAGGATACAGCATTGTTATCGTTGTTGAGATATTAGTAAGAAATACGCCTTTCCCCATGTTGTAAACGGGCTA
118
Dillon Cower
źródło
3

R 51

Odczytuje to dwa wiersze od użytkownika (które są danymi wejściowymi), a następnie po prostu używa adistfunkcji do obliczenia odległości. Ponieważ podstawienia kosztują 2 za ten problem, musimy dodać nazwany wektor dla parametru kosztów dla adist. Ponieważ istnieje także parametr counts dla adist, możemy jedynie skrócić koszty do cos, więc nadal mamy unikalne dopasowanie dla nazw parametrów.

x=readLines(n=2);adist(x[1],x[2],cos=c(i=1,d=1,s=2))

Przykładowe użycie

> x=readLines(n=2);adist(x[1],x[2],cos=c(i=1,d=1,s=2))
MART
KARMA
     [,1]
[1,]    5
Dason
źródło
0

Ruby 1.9, 124

l=->a,b{a[0]?b[0]?[(a[0]==b[0]?-1:1)+l[a[1..-1],b[1..-1]],l[a[1..-1],b],l[a,b[1..-1]]].min+1: a.size: b.size}
puts l[*ARGV]

Golfowa wersja powolnej, rekurencyjnej metody Ruby tutaj , zmodyfikowana w celu podwojenia wagi zastępstw. Fakt, że usunięcie pierwszego znaku ciągu zajmuje 7 znaków, naprawdę boli i fajnie byłoby zastąpić (a[0]==b[0]?-1:1)go czymś takim, -1**a[0]<=>b[0]ale kolejność operacji nie jest moim przyjacielem.

histocrat
źródło
0

Smalltalk (Smalltalk / X), 34

Mam szczęście - standardowa klasa „String” zawiera już levenshtein:

wprowadź a, b:

a levenshteinTo:b s:2 k:2 c:1 i:1 d:1

(dodatkowe parametry pozwalają na różne wagi przy podstawianiu, usuwaniu itp.)

Testowe uruchomienie:

#( 'ISLANDER'  'SLANDER' 
   'MART'      'KARMA'   
   'KITTEN'    'SITTING' 
   'INTENTION' 'EXECUTION'  
) pairWiseDo:[:a :b|
    a print. ' ' print. b print. ' ' print.
    (a levenshteinTo:b
            s:2 k:2 c:1 i:1 d:1) printCR.
].

->

ISLANDER SLANDER 1
MART KARMA 5
KITTEN SITTING 5
INTENTION EXECUTION 8
blabla999
źródło