Prolog毫无理由地退出本地堆栈

Question

我正在尝试在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。

Answer 1

您的程序无法正常运行有一个很好的理由：您的递归调用会导致无限循环。

这是由以下几行引起的：

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表达式之类的表达式不会对数字求值。因此，您的代码将递归调用lev第三个参数L1 -1，依次为L1 - 1 - 1，，等，这与您的终止规则不匹配。

要解决此问题，您需要使用临时变量来评估例如的结果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.

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