Aviseringar
Rensa alla

Programmeringsutmaning mini: Levenshtein-distans


Ämnesstartare

Här kommer en enkel programmeringsutmaning: skriv i valfritt språk en funktion som beräknar Levenshtein-avståndet mellan två strängar.

Bonusuppgift: funktionen ska dra mindre minne än O(m*n) där m är längden på ena strängen och n längden på den andra. Den ska dessutom vara snabbare och/eller kortare än min (kommentarer räknas givetvis inte.)

Jag använde följande två strängar, kopierade tio gånger vardera, för att testa funktionen:

– Vi ser stora brister i kvaliteten idag. Det skulle krävas runt 5 miljarder kronor för att komma upp i den kvalitet vi hade i mitten av 1990-talet. De rödgröna vill stärka kvaliteten med 400 miljoner per år, men det räcker inte riktigt. Man har också pratat om högre studielån, men utan att komma med några exakta siffror, säger Beatrice Högå. Inte heller den borgerliga alliansen har kommit med några konkreta bud till studenterna. – Folkpartiet och högskoleministern har sagt att satsningar på grundutbildningen är prioriterade, men vi väntar på att se hur satsningen kommer att se ut. Å andra sidan har Anders Borg sagt att man inte ska satsa på högskolan, säger Beatrice Högå.

...och...

Patentansökan beskriver även en teknik som ska göra det möjligt att identifiera en Iphone som blivit modifierad eller hackad, en teknik som populärt kallas jailbreak. Jailbreak gör det bland annat möjligt att köra program som inte är godkända av Apple. Apple har nyligen gått ut och meddelat att användare som utför ett jailbreak på sin Iphone förlorar garantin på telefonen. I Apples patentansökan ska den nya tekniken göra det möjligt att låsa en telefon som utsatts för ett jailbreak. Huruvida Apple kommer att använda tekniken i praktiken är än så länge okänt.

Med den indatan kör funktionen på ~1,25 sekunder på en Core 2 Duo 2,4 GHz, rätt svar är 5030. (Rätt svar om man INTE kopierar texterna 10x är naturligtvis 503.)

Mitt bidrag, i Haskell (om än inte särskilt idiomatisk Haskell, eftersom jag försökt optimera den så mycket som möjligt och skrev den just för att lära mig använda ST-monaden:)

module Levenshtein (distance) where
import Data.Array.ST
import Control.Monad.ST
import Control.Monad
import Data.Bits

-- | Calculate the Levenshtein distance between two lists.
distance :: (Eq a) => [a] -> [a] -> Int
distance [] [] = 0
distance as bs =
runST $ do
let ((as', lenA), (bs', lenB)) =
case (length as, length bs) of
(a, b) | b > a -> ((bs, b+1), (as, a+1))
| otherwise -> ((as, a+1), (bs, b+1))
fill = head as'

arr <- newArray_ ((0, 0), (1, lenB)) :: ST s (STUArray s (Int, Int) Int)
forM_ [0..lenB] $ \j -> writeArray arr (0, j) j

forM_ (zip [1..] $ fill:as') $ \(i, a) -> do
let iidx = i .&. 1
iidxMinusOne = iidx `xor` 1
writeArray arr (iidx, 0) i

forM_ (zip [1..] $ fill:bs') $ \(j, b) -> do
upleft <- readArray arr (iidxMinusOne, j-1)
if a == b
then do
writeArray arr (iidx, j) upleft
else do
left <- readArray arr (iidxMinusOne, j)
up <- readArray arr (iidx, j-1)
writeArray arr (iidx, j) $ (min upleft $ min up left) + 1

readArray arr $ (lenA `mod` 2, lenB)

EDIT: kommentarerna gjorde koden oläsbar, så de fick gå.


   
Citera
Åtta

Kan nog skriva en horribelt ineffektiv variant i Python senare. Men just nu är jag inne i de 9 sista timmarna av Ludum Dare Jam, så jag känner inte riktigt att jag orkar nu.


   
SvaraCitera

Gör ditt skolarbete själv? [wink]


   
SvaraCitera
Ämnesstartare

stentuff:

Gör ditt skolarbete själv? [wink]

Du verkar helt ha missat att jag själv postat en lösning.


   
SvaraCitera

hittade denna pseudokod på wikipedia.

int LevenshteinDistance(char s[1..m], char t[1..n])
{
// d is a table with m+1 rows and n+1 columns
declare int d[0..m, 0..n]

for i from 0 to m
d[i, 0] := i // deletion
for j from 0 to n
d[0, j] := j // insertion

for j from 1 to n
{
for i from 1 to m
{
if s = t[j] then
d[i, j] := d[i-1, j-1]
else
d[i, j] := minimum
(
d[i-1, j] + 1, // deletion
d[i, j-1] + 1, // insertion
d[i-1, j-1] + 1 // substitution
)
}
}

return d[m,n]
}

hur gör man sådana där små fönster btw?


   
SvaraCitera

Och hur motiverar du att din algoritm ger det minsta antalet operationer? Bevis!


   
SvaraCitera