7

文字列が Prolog の別の文字列の部分文字列であるかどうかを確認する方法はありますか? 文字列を文字のリストに変換してから、最初のセットが2番目のサブセットであり、十分に制限されていないように見えるかどうかを確認してみました。これは私の現在のコードです：

isSubstring(X,Y):-
        stringToLower(X,XLower),
        stringToLower(Y,YLower),
        isSubset(XLower,YLower).

isSubset([],_).
isSubset([H|T],Y):-
        member(H,Y),
        select(H,Y,Z),
        isSubset(T,Z).

stringToLower([],[]).
stringToLower([Char1|Rest1],[Char2|Rest2]):-
        char_type(Char2,to_lower(Char1)),
        stringToLower(Rest1,Rest2).

これをテストすると

isSubstring("test","tesZting")。

yes を返しますが、no を返す必要があります。

4

4 に答える 4

6

文字列の意味が明確ではありません。しかし、それをリストに変換していると言っているので、アトムを意味する可能性があります。ISO Prolog は、この目的のためにatom_concat/3とを提供しています。sub_atom/5

| ?- atom_concat(X,Y,'abc').
  X = '', Y = abc
; X = a, Y = bc
; X = ab, Y = c
; X = abc, Y = ''.

| ?- sub_atom('abcbcbe',Before,Length,After,'bcb').
  Before = 1, Length = 3, After = 3
; Before = 3, Length = 3, After = 1.

それ以外の場合は、DCG を使用してください。方法は次のとおりです

seq([]) --> [].
seq([E|Es]) --> [E], seq(Es).

... --> [] | [_], ... .

subseq([]) --> [].
subseq(Es) --> [_], subseq(Es).
subseq([E|Es]) --> [E], subseq(Es).

seq_substring(S, Sub) :-
   phrase((...,seq(Sub),...),S).

seq_subseq(S, Sub) :-
   phrase(subseq(Sub),S).

謝辞

上記の定義の最初の出現...は、p. 205、注1

デビッド・B・サールズ、確定節文法によるDNAの言語学の調査。NACLP 1989、第 1 巻。

于 2013-11-27T19:43:22.567 に答える
1

問題はあなたにありますisSubset/2。
1 つの述語で捉えようとした 2 つの異なる状況があります。部分文字列を一致させるために最初の位置を探しているか、すでにそのポイントを見つけて、文字列が「整列」しているかどうかを確認しています。

isSubset([], _).
isSubSet(Substring, String) :-
    findStart(Substring, String, RestString),
    line_up(Substring, RestString).

findStart([], String, String).
findStart([H|T], [H|T1], [H|T1]).
findStart(Substring, [_|T], RestString) :-
    findStart(Substring, T, RestString).

line_up([], _).
line_up([H|T], [H|T1]) :-
    line_up(T, T1).

次のように、これらを 1 つの述語に組み合わせることができます。

isSublist([], L, L).
isSublist([H|T], [H|T1], [H|T1]) :-
    isSublist(T, T1, T1).
isSublist(L, [_|T], Rest) :-
    isSublist(L, T, Rest).
于 2013-11-28T07:52:55.300 に答える
1

プロローグ文字列はリストであり、リストの各要素は問題の文字のコードポイントを表す整数値です。文字列"abc"はリストとまったく同じです[97,98,99](プロローグの実装で Unicode または ASCII を使用していると仮定すると、値は異なる可能性があります)。これは、基本的に X が S の部分文字列であると言う (Big-O の観点からはおそらく次善の) ソリューションにつながります。

  • S には接尾辞 T があり、
  • X は T のプレフィックスです

コードは次のとおりです。

substring(X,S) :-
  append(_,T,S) ,
  append(X,_,T) ,
  X \= []
  .

X を空のリスト (別名 nil string ) 以外のものに制限します。これは""、概念的には、任意の文字列で非常に多くの長さゼロの部分文字列を見つけることができるためです: 長さnの文字列には 2+( n -1) nil 部分文字列があります。 、文字列内の各文字の間に 1 つ、最初の文字の前に 1 つ、最後の文字の後に 1 つ。

于 2013-11-27T22:39:57.417 に答える