0

我正在尝试在 Prolog中实现Levenshtein 距离。

实现非常简单：

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的表达式。因此，您的代码将使用与您的终止规则不匹配的第三个参数 as 、 then等递归调用。levL1 -1L1 - 1 - 1

要解决此问题，您需要使用临时变量来评估例如的结果L1 - 1。

这修复了它：

lev(W1, W2, L1, L2, D) :-
     L11 是 L1 - 1, 
    L22 是 L2 - 1, 
    lev(W1, W2, L11 , L2, D1),
    列弗（W1，W2，L1，L22，D2），
    列弗（W1，W2，L11，L22，D3），
    字符（W1，L1，C1），
    字符（W2，L2，C2），
    （C1 = C2 -> T 为 0；T 为 1），
    D4 是 D3 + T，
    最小值（D1，D2，D4，D）。

现在这样做：

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

这可能不是您想要的结果，但至少它不会出错。我会把它留给你来修复你的谓词。

于 2016-11-28T15:22:35.257 回答
3

你的程序有几个问题。

循环

@Fatalize 已经给了你一个理由，这里是一个通用的方法，你可以使用一个来定位这些问题，通过它可以将一些目标false插入到你的程序中。如果剩余的程序循环，原始版本也会：

?- levenshtein("poka","po",X), false。

levenshtein（W1，W2，D）：-
    atom_length(W1, L1),
    atom_length(W2, L2),
    列夫（W1，W2，L1，L2，D），假，
     ！.

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 的“olde”算法。而是use_module(library(clpfd))获得更纯净的代码。

于 2016-11-28T16:40:31.020 回答