2

我想编写一个 Prolog 谓词,它接受一个单词并在键盘上向左或向右移动它......

...,但是 - 到目前为止 - 我不知道从哪里开始。


例子。键盘上将“loogika”这个词移到左边!

请注意,如果我们的键盘布局qwerty ,我们会在 left-shifting 时碰到边缘a。我们可以用不同的方式来处理这个问题,但似乎每个“解决方案”都有自己的优点缺点。

那么我们该怎么办?a 不是让左移,而是留下。IMO,不要切换那个讨厌东西值得失去代数属性,在以保留 2D 物理距离的方式处理其他边缘/角落情况时很难维持这些属性...... YMMV!Caps LockaCaps-Lock

示例 Prolog 查询:

?-tipi([ l, o, o, g, i, k, a],
        [ k, i, i, f, u, j, a])。
真的。

当我们在 qwerty 键盘上写“loogika”/“kiifuja”时按下了哪些键?看看,看看!

左移前后,动画

4

1 回答 1

1

对于原始问题:

:-use_module(library(clpfd)).

table([[1,2,3,4,5,6,7,8,9,0],[q,w,e,r,t,y,u,i,o,p], [a,s,d,f,g,h,j,k,l,;],[z,x,c,v,b,n,m,',','.','/']]).

shift_left(Char,New_Char):-
  table(Table),
  member(R,Table),
  nth1(I,R,Char),
  shift_l(I,NI),
  nth1(NI,R,New_Char).

shift_right(Char,New_Char):-
  table(Table),
  member(R,Table),
  nth1(I,R,Char),
  shift_r(I,NI),
  nth1(NI,R,New_Char).

shift_seq(left,Seq,NewSeq):-
  maplist(shift_left,Seq,NewSeq).
shift_seq(right,Seq,NewSeq):-
  maplist(shift_right,Seq,NewSeq).

shift_l(1,1).
shift_l(X,Y):-
  X>1,
  X#=Y+1.

shift_r(10,10).
shift_r(X,Y):-
  X<10,
  X#=Y-1.

询问:

?- shift_seq(left,[l,o,o,g,i,k,a],N).
N = [k, i, i, f, u, j, a] .

我认为问题中的 g 是错字;)

对于赏金,您可以使用此表中的曼哈顿距离。然后将该距离与 Levenshtein 距离的权重相结合。我想出了以下改编。我不确定它是否是“真实距离函数”。

:-use_module(library(clpfd)).
:-use_module(library(aggregate)).

table([['1','2','3','4','5','6','7','8','9','0'],[q,w,e,r,t,y,u,i,o,p], [a,s,d,f,g,h,j,k,l,;],[z,x,c,v,b,n,m,',','.','/']]).

vert_distance(A,B,Table,Distance):-
  length(Table,L),
  Distance in 0..L,
  member(Row1,Table),
  member(Row2,Table),
  member(A,Row1),
  member(B,Row2),
  nth0(N1,Table,Row1),
  nth0(N2,Table,Row2),
  Distance #= abs(N1-N2).

hoz_distance(A,B,Table,Distance):-
  member(Row1,Table),
  member(Row2,Table),
  length(Row1,L),
  Distance in 0..L,
  nth0(N1,Row1,A),
  nth0(N2,Row2,B),
  Distance #= abs(N1-N2).

manhatten(A,B,Table,D):-
  vert_distance(A,B,Table,V),
  hoz_distance(A,B,Table,H),
  D#=V+H.

manhatten_string([],[],_,0).
manhatten_string(String1,String2,Table,D):-
  length(String1,L),
  length(String2,L),
  manhatten_string_(String1,String2,Table,D1),
  D is D1/L.
manhatten_string(S1,S2,Table,D):-
  length(S1,L1),
  length(S2,L2),
  D#=abs(L1-L2).

manhatten_string_([],[],_,0).
manhatten_string_(String1,String2,Table,D1):-
  String1 =[H1|T1],
  String2 =[H2|T2],
  manhatten(H1,H2,Table,DL),
  manhatten_string(T1,T2,Table,D0),
  D1 is D0+(DL/14).

lev(String1,String2,D):-
  length(String1,L1),
  length(String2,L2),
  0 is min(L1,L2),
  D is max(L1,L2).
lev(String1,String2,D):-
  String1 =[H1|T1],
  String2 =[H2|T2],
  lev(T1,String2,D1),
  lev(String1,T2,D2),
  lev(T1,T2,D3),
  D1plus1 is D1+1,
  D2plus1 is D2+1,
  indicator([H1],[H2],DM),
  D3plus is D3+DM,
  aggregate_all(min(X),member(X,[D1plus1,D2plus1,D3plus]),D).

indicator(Ai,Bj,0):-
  Ai=Bj.
indicator(Ai,Bj,D):-
  Ai\=Bj,
  table(Table),
  manhatten_string(Ai,Bj,Table,D).

查询:

?- lev([a,a],[b,a],D).
D = 0.35714285714285715 .

?- lev([a,a],[a,b],D).
D = 0.35714285714285715 .

?- lev([a,a],[a,b,c,d],D).
D = 2.142857142857143 .

?- lev([a],[],D).
D = 1 .

?- lev([a],[s],D).
D = 0.07142857142857142 .

?- lev([a],[o],D).
D = 0.6428571428571429 .

?- lev([a,b],[a,b],D).
D = 0 .

?- lev([a,b,c],[a,b],D).
D = 1 .

?- lev([a,b,c],[a,b,p],D).
D = 0.6428571428571429 .

还有图书馆(isub)http://www.swi-prolog.org/pldoc/doc_for?object=section(0,%270%27,swi(%27/doc/packages/nlp.html%27)) . 这看起来适合其中的一部分。

于 2015-10-01T22:07:32.317 回答