0

Prolog にレーベンシュタイン距離を実装しようとしています。

実装は非常に簡単です。

levenshtein(W1, W2, D) :-
    atom_length(W1, L1),
    atom_length(W2, L2),
    lev(W1, W2, L1, L2, D),
    !.

lev(_, _, L1, 0, D) :- D is L1, !.
lev(_, _, 0, L2, D) :- D is L2, !.
lev(W1, W2, L1, L2, D) :-
  lev(W1, W2, L1 - 1, L2, D1),
  lev(W1, W2, L1, L2 - 1, D2),
  lev(W1, W2, L1 - 1, L2 - 1, D3),
  charAt(W1, L1, C1),
  charAt(W2, L2, C2),
  ( C1 = C2 -> T is 0; T is 1 ),
  min(D1, D2, D3 + T, D).

% Returns the character at position N in the atom A
% The position is 1-based
% A: The atom
% N: The position at which to extract the character
% C: The character of A at position N
charAt(A, N, C) :- P is N - 1, sub_atom(A, P, 1, _, C).

% min(...): These rules compute the minimum of the given integer values
% I1, I2, I3: Integer values
% M:          The minimum over the values
min(I1, I2, M) :- integer(I1), integer(I2), ( I1 =< I2 -> M is I1; M is I2).
min(I1, I2, I3, M) :- min(I1, I2, A), min(I2, I3, B), min(A, B, M).

ただし、このコードは次のエラーで失敗します。

?- levenshtein("poka", "po", X).
ERROR: Out of local stack

SWIPLで実装を使用していMac OS X Sierraます。

4

2 に答える 2

5

プログラムが機能しないのには十分な理由があります。再帰呼び出しが無限ループにつながるからです。

これは、次の行が原因です。

lev(W1, W2, L1 - 1, L2, D1),

lev(W1, W2, L1, L2 - 1, D2),

lev(W1, W2, L1 - 1, L2 - 1, D3),

min(D1, D2, D3 + T, D)

Prolog のようなものは、数値に評価されないL1 - 1式です。したがって、コードは、 thenなどの 3 番目の引数を使用して再帰的に呼び出しますが、これは終了規則と一致しません。levL1 -1L1 - 1 - 1

これを修正するには、eg の結果を評価する一時変数を使用する必要がありますL1 - 1。

これで修正されます：

lev(W1, W2, L1, L2, D) :-
     L11 は L1 - 1、
    L22 は L2 - 1、 
    lev(W1, W2, L11 , L2, D1)、
    lev(W1, W2, L1, L22 , D2),
    lev(W1, W2, L11 , L22 , D3),
    charAt(W1、L1、C1)、
    charAt(W2、L2、C2)、
    ( C1 = C2 -> T は 0; T は 1 )、
    D4 は D3 + T, 
    min(D1, D2, D4 , D) です。

今これはこれを行います：

?- levenshtein("poka","po",X).
X = 0.

これはおそらくあなたが望む結果ではありませんが、少なくともエラーにはなりません。述語を修正するのはあなたに任せます。

于 2016-11-28T15:22:35.257 に答える
3

あなたのプログラムにはいくつかの問題があります。

ループ

@Fatalize はすでに理由を示しています。これは、いくつかの目標をプログラムに挿入するfalse残りのプログラムがループする場合、元のバージョンでも次のことが行われました。

?- レーベンシュタイン("ポカ","ポ",X), false .

レーベンシュタイン(W1, W2, D) :-
    atom_length(W1, L1),
    atom_length(W2, L2),
    lev(W1, W2, L1, L2, D), false ,
     ! .

lev(_, _, L1, 0, D) :- D は L1, !.
lev(_, _, 0, L2, D) :- D は L2, !.
レブ（W1、W2、L1、L2、D）： -
  lev(W1, W2, L1 - 1, L2, D1), false ,
   lev(W1, W2, L1, L2 - 1, D2) ,
   lev(W1, W2, L1 - 1, L2 - 1, D3) ,
   charAt (W1, L1, C1) ,
   charAt(W2, L2, C2) ,
   ( C1 = C2 -> T は 0; T は 1 ) ,
   min(D1, D2, D3 + T, D) .

残りの目に見える部分で何かを変更する必要があります。そうしないと、この問題は解決しません。

リストを使おう！

アトムや文字列を使用する代わりに、リストを使用して単語を表現することをお勧めします。.swiplrcorに追加するのが最善です.sicstusrc：

:- set_prolog_flag(double_quotes, chars).

このように、次のことが成立します。

?- "abc" = [a,b,c].

カットを避ける

何らかの方法でカットを行い、動作することもありますが、そのようなプログラムはデバッグが困難です。特に初心者向け。したがって、それらを絶対に避けてください

きれいな算術を使う

高度にモード化された Prolog の「古い」演算を使用しています。代わりuse_module(library(clpfd))に、より純粋なコードを取得します。

于 2016-11-28T16:40:31.020 に答える