0

2 次元リスト x を表す特定のリストがあります。以下の例でわかるように、このテーブルには 1 の 2 つの「スポット」が含まれています。

xxxxxxxxxxxxxxxx
xx1111xxxx111xxx
xxx1111xxxx11xxx
x1111xxxxxx111xx

以下の例のように、2 番目のスポットのみを 1 から 2 に変更する必要があります。

xxxxxxxxxxxxxxxx
xx1111xxxx222xxx
xxx1111xxxx22xxx
x1111xxxxxx222xx

separate(L,M)最初のリスト L を取り、2 番目のテーブル M を生成するという述語が必要です

「findall」などの標準的な述語を使用せずにこれを解決できれば素晴らしいでしょう...

4

3 に答える 3

3

Definite Clause Grammars (DCG) を使用して、有限状態変換器を実装できます。DCG は、プロダクション側で構成操作をあまり提供しませんが、認識側の実装には非常に優れています。

したがって、認識したいのは、2 つの異なるタイプの 1 の連続です。したがって、基本的に、入力行は Extended Backus Naur Form (EBNF) で次のようになると思います。

line :== exs run1 exs run2 exs | exs.
exs  :== { "x" } "x".
run1 :== { "1" } "1".
run2 :== { "1" } "1".

認識の問題については、属性なしで DCG を書くことができます (以下は Prolog テキストです。ファイルに入れるか、?- [user] 経由で直接調べることができます)。

line --> exs, run1, exs, run2, exs | exs.

run1 --> "1", run1.
run1 --> "1".

run2 --> "1", run2.
run2 --> "1".

exs --> "x", exs.
exs --> "x".

いくつかの実行例を次に示します。

?- phrase(line,"xxx").
Yes 
?- phrase(line,"xxx111xxx111xxx").
Yes 
?- phrase(line,"xxx111xxx"). 
No

生産上の問題については、属性を DCG に追加するだけです。差分リストを使用すると、最も簡単に機能します。

line(I,O) --> exs(I,H), run1(H,J), exs(J,K), run2(K,L), exs(L,O) | exs(I,O).

run1([0'1|I],O) --> "1", run1(I,O).
run1([0'1|H],H) --> "1".

run2([0'2|I],O) --> "1", run2(I,O).
run2([0'2|H],H) --> "1".

exs([0'x|I],O) --> "x", exs(I,O).
exs([0'x|H],H) --> "x".

いくつかの実行例を次に示します。

?- phrase(line(R,[]),"xxx").
R = [120, 120, 120] 
?- phrase(line(R,[]),"xxx111xxx111xxx").
R = [120, 120, 120, 49, 49, 49, 120, 120, 120, 50, 50, 50, 120, 120, 120] 
?- phrase(line(R,[]),"xxx111xxx").
No

注: 0' は、文字コードの Prolog 表記です。アスキーでは、0'x = 120、0'1 = 49、0'2 = 50 となり、結果が説明されます。上記は DCG をサポートしているため、ほとんどの Prolog システムで動作するはずです。

さよなら

定句文法
http://en.wikipedia.org/wiki/Definite_clause_grammar

有限状態変換器
http://en.wikipedia.org/wiki/Finite_state_transducer

于 2012-01-08T14:19:25.603 に答える
1

アドホックな音訳を適用できます (「水平」リストのみ)。

transliteration(Matrix, Translit) :-
  maplist(transliteration(not_seen), Matrix, Translit).

transliteration(_State, [], []).
transliteration(State, [X|Xs], [Y|Ys]) :-
  transliteration(State, X, NewState, Y),
  transliteration(NewState, Xs, Ys).

% handle only required state change
transliteration(not_seen, 0'1, seen_first, 0'1).
transliteration(seen_first, C, seen_last, C) :- C =\= 0'1.
transliteration(seen_last, 0'1, seen_last, 0'2).
% catch all, when no change required
transliteration(State, C, State, C).
于 2012-01-08T15:39:21.227 に答える
0

@chac によって提案されたソリューションに似ていますが、より直接的です。

walk(L, R) :- walk(s0, L, R).
walk(_, [], []). % finish
walk(s0, [0'1|T], [0'1|R]) :- walk(s1, T, R).
walk(s1, [0'x|T], [0'x|R]) :- walk(s2, T, R).
walk(s2, [0'1|T], [0'2|R]) :- walk(s2, T, R).
walk(S, [H|T], [H|R]) :- walk(S, T, R). % keep state and do nothing
于 2012-01-08T16:10:52.897 に答える