6

Haskell でレーベンシュタイン距離の計算をいじっていますが、次のパフォーマンスの問題に少し不満を感じています。以下の (dist) のように、Haskell の最も「通常の」方法で実装すると、すべて正常に動作します。

dist :: (Ord a) => [a] -> [a] -> Int
dist s1 s2 = ldist s1 s2 (L.length s1, L.length s2)

ldist :: (Ord a) => [a] -> [a] -> (Int, Int) -> Int
ldist _ _ (0, 0) = 0
ldist _ _ (i, 0) = i
ldist _ _ (0, j) = j
ldist s1 s2 (i+1, j+1) = output
  where output | (s1!!(i)) == (s2!!(j)) = ldist s1 s2 (i, j)
               | otherwise = 1 + L.minimum [ldist s1 s2 (i, j)
                                          , ldist s1 s2 (i+1, j)
                                          , ldist s1 s2 (i, j+1)]

しかし、頭を少し曲げて dist' として実装すると、実行速度が大幅に向上します (約 10 倍)。

dist' :: (Ord a) => [a] -> [a] -> Int
dist' o1 o2 = (levenDist o1 o2 [[]])!!0!!0 

levenDist :: (Ord a) => [a] -> [a] -> [[Int]] -> [[Int]]
levenDist s1 s2 arr@([[]]) = levenDist s1 s2 [[0]]
levenDist s1 s2 arr@([]:xs) = levenDist s1 s2 ([(L.length arr) -1]:xs)
levenDist s1 s2 arr@(x:xs) = let
    n1 = L.length s1
    n2 = L.length s2
    n_i = L.length arr
    n_j = L.length x
    match | (s2!!(n_j-1) == s1!!(n_i-2)) = True | otherwise = False
    minCost = if match      then (xs!!0)!!(n2 - n_j + 1) 
                            else L.minimum [(1 + (xs!!0)!!(n2 - n_j + 1))
                                          , (1 + (xs!!0)!!(n2 - n_j + 0))
                                          , (1 + (x!!0))
                                          ]
    dist | (n_i > n1) && (n_j > n2)  = arr 
         | n_j > n2  = []:arr `seq` levenDist s1 s2 $ []:arr
         | n_i == 1 = (n_j:x):xs `seq` levenDist s1 s2 $ (n_j:x):xs
         | otherwise = (minCost:x):xs `seq` levenDist s1 s2 $ (minCost:x):xs
    in dist 

最初のバージョンで通常のトリックをすべて試しましたseqが、速度が向上するものはないようです。最初のバージョンはマトリックス全体を評価する必要がなく、必要な部分だけを評価する必要があるため、 高速になると思っていたので、これは私にとって少し不満です。

これら2つの実装を同様に実行できるかどうかは誰にもわかりますか、それとも後者の末尾再帰最適化の利点を享受しているだけなので、パフォーマンスが必要な場合は読みにくいことに耐える必要がありますか?

ありがとう、オリオン

4

5 に答える 5

5

過去に、私はウィキブックスと一緒に、またはウィキブックスから、この非常に簡潔なバージョンを使用foldlましscanlた:

distScan :: (Ord a) => [a] -> [a] -> Int
distScan sa sb = last $ foldl transform [0 .. length sa] sb
  where
    transform xs@(x:xs') c = scanl compute (x + 1) (zip3 sa xs xs')
       where
         compute z (c', x, y) = minimum [y + 1, z + 1, x + fromEnum (c' /= c)]

Criterionを使用して、この単純なベンチマークを実行しました。

test :: ([Int] -> [Int] -> Int) -> Int -> Int
test f n = f up up + f up down + f up half + f down half
  where
    up = [1..n]
    half = [1..div n 2]
    down = reverse up

main = let n = 20 in defaultMain
  [ bench "Scan" $ nf (test distScan) n
  , bench "Fast" $ nf (test dist') n
  , bench "Slow" $ nf (test dist) n
  ]

そして、ウィキブックス版はあなたの両方をかなり劇的に上回っています:

benchmarking Scan
collecting 100 samples, 51 iterations each, in estimated 683.7163 ms...
mean: 137.1582 us, lb 136.9858 us, ub 137.3391 us, ci 0.950

benchmarking Fast
collecting 100 samples, 11 iterations each, in estimated 732.5262 ms...
mean: 660.6217 us, lb 659.3847 us, ub 661.8530 us, ci 0.950...

Slow数分後も実行中です。

于 2010-09-30T15:43:38.213 に答える
3

計算lengthするには、リスト全体を評価する必要があります。これは、高価なO(n)操作です。さらに重要なことは、その後、リストの参照を停止するまで(=>より大きなメモリフットプリント)、リストはメモリ内に保持されます。経験則ではlength、リストが長くなることが予想される場合は、リストで使用しないでください。同じことが参照され(!!)ます、それは毎回リストの一番上から行くので、それもO(n)です。リストは、ランダムアクセスデータ構造として設計されていません。

Haskellリストを使ったより良いアプローチは、それらを部分的に消費することです。折り目は通常、同様の問題に取り組む方法です。そして、レーベンシュタイン距離はそのように計算することができます(以下のリンクを参照)。より良いアルゴリズムがあるかどうかはわかりません。

別のアプローチは、リストではなく、別のデータ構造を使用することです。たとえば、ランダムアクセス、既知の長さなどが必要な場合は、を参照してくださいData.Sequence.Seq

既存の実装

2番目のアプローチは、Haskellでのレーベンシュタイン距離のこの実装で使用されています(配列を使用)。foldlそこにある最初のコメントでベースの実装を見つけることができます。ところで、foldl'通常はよりも優れていfoldlます。

于 2010-09-30T14:56:52.490 に答える
2

d がレーベンシュタイン距離である場合、O(N*d) アルゴリズムを使用することができます。これは、Lloyd Allison による Lazy MLの実装で、遅延性を利用して複雑さを改善しています。これは、行列の一部、つまり、幅がレーベンシュタイン距離に比例する主対角線の周囲の領域のみを計算することによって機能します。

編集:これがhaskell に変換され、行列のどの要素が計算されるかを示す素敵な画像が表示されていることに気付きました。シーケンスが非常に類似している場合、これは上記の実装よりも大幅に高速になるはずです。上記のベンチマークを使用すると、次のようになります。

benchmarking Scan
collecting 100 samples, 100 iterations each, in estimated 1.410004 s
mean: 141.8836 us, lb 141.4112 us, ub 142.5126 us, ci 0.950

benchmarking LAllison.d
collecting 100 samples, 169 iterations each, in estimated 1.399984 s
mean: 82.93505 us, lb 82.75058 us, ub 83.19535 us, ci 0.950
于 2010-10-01T02:14:30.310 に答える
2

私はまだあなたの 2 回目の試みのすべてを追っていませんが、私が思い出す限り、レーベンシュタイン アルゴリズムの背後にある考え方は、行列を使用して繰り返し計算を節約することです。コードの最初の部分では、計算を共有していないため、多くの計算を繰り返すことになります。たとえば、計算するときは、少なくとも 3 回 (直接 1 回、経由 1 回、経由 1 回)のldist s1 s2 (5,5)計算を行います。ldist s1 s2 (4,4)ldist s1 s2 (4,5)ldist s1 s2 (5,4)

あなたがすべきことは、マトリックスを生成するためのアルゴリズムを定義することです(必要に応じて、リストのリストとして)。これはあなたの2番目のコードが行っていることだと思いますが、帰納的なスタイルで行列をきれいに構築するのではなく、トップダウンの方法で行列を計算することに焦点を当てているようです(基本ケースの再帰呼び出しは非常に珍しいです)私の目に)。残念ながら、私はすべてを書き出す時間がありませんが、ありがたいことに他の誰かが持っています: このアドレスで最初のバージョンを見てください: http://en.wikibooks.org/wiki/Algorithm_implementation/Strings/Levenshtein_distance#Haskell

さらに2つのこと:1つは、各エントリが対角線、垂直線、および水平線に依存しているため、レーベンシュタインアルゴリズムがマトリックスの一部のみを使用できるかどうかはわかりません。1 つのコーナーの値が必要な場合は、必然的に他のコーナーまでマトリックスを評価する必要があります。次に、そのmatch | foo = True | otherwise = False行は単純に に置き換えることができますmatch = foo

于 2010-09-30T15:11:04.373 に答える
0

data-memocombinatorsパッケージを使用した、より直感的なソリューション。クレジットはこの回答に送られます。ここに示されているすべてのソリューションは、おそらく C で記述されたpython-Levenshteinよりもはるかに遅いように見えるため、ベンチマークは大歓迎です。

import Data.MemoCombinators (memo2, integral)

levenshtein :: String -> String -> Int
levenshtein a b = levenshtein' (length a) (length b) where
  levenshtein' = memo2 integral integral levenshtein'' where
    levenshtein'' x y -- take x characters from a and y characters from b
      | x==0 = y
      | y==0 = x
      | a !! (x-1) == b !! (y-1) = levenshtein' (x-1) (y-1)
      | otherwise = 1 + minimum [ levenshtein' (x-1) y, 
        levenshtein' x (y-1), levenshtein' (x-1) (y-1) ]
于 2015-10-27T01:26:18.553 に答える