- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我正在开始 Erlang,作为练习,我尝试实现 CYK algorithm .
主要代码(cyk.erl):
%%% An attempt for a CYK parser in Erlang
-module(cyk).
-export([
init_storage/0,
import_grammar_file/1,
add_grammar_rule/1,
analyze/1,
test_analyze/0
]).
%% Initialize the ets storage for grammar
init_storage() ->
ets:new(?MODULE, [bag, named_table]).
%%------------------------------------------
%%
%% Grammar
%%
%%------------------------------------------
%% Import a grammar file
import_grammar_file(File) ->
{ok, Device} = file:open(File, read),
import_file_rules(Device).
%% Import all the rules in the file
import_file_rules(Device) ->
case io:get_line(Device, "") of
eof ->
io:format("Grammar file imported~n"),
file:close(Device);
Line ->
add_grammar_rule(Line),
import_file_rules(Device)
end.
%% Add a grammar rule
add_grammar_rule(Rule) ->
case re:run(Rule, "^([^\s]+)\s?->\s?([^\n]+)$", [{capture, all_but_first, binary}]) of
{match, [A, B]} ->
ets:insert(?MODULE, {A, B}),
io:format("parsing ~p -> ~p~n", [A, B]);
nomatch ->
io:format("cannot parse ~p~n", [Rule])
end.
%%------------------------------------------
%%
%% Main logic
%%
%%------------------------------------------
%% Analyze a sentence
analyze(Sentence) ->
io:format("analysing: ~p~n", [Sentence]),
WordList = re:split(Sentence, " "),
io:format("wordlist: ~p~n", [WordList]),
Representation = lists:map( fun(Word) -> associate(Word) end, WordList),
io:format("representation: ~p~n", [Representation]),
Result = process([Representation]),
io:format("result: ~p~n", [Result]).
% associate sentence words with grammar terms
associate(Word) ->
case ets:match(cyk, {'$1', Word}) of
[H|T] -> lists:flatten([H|T]);
[] -> []
end.
% process sentence representation
process(Representation) ->
Limit = length(lists:last(Representation)),
process(Representation, Limit).
process(Representation, Limit) when Limit > 1 ->
NextStep = process(Representation, 1, Limit-1, []),
process([NextStep|Representation], Limit-1);
process(Representation, _Limit) ->
Representation.
process(Representation, Index, Limit, Acc) when Index =< Limit ->
Subtree = extract_subtree(lists:reverse(Representation), Index),
Result = process_subtree(Subtree),
process(Representation, Index+1, Limit, [Result|Acc]);
process(_Representation, _Index, _Limit, Acc) ->
lists:reverse(Acc).
%%------------------------------------------
%%
%% Subtree
%%
%%------------------------------------------
process_subtree(Subtree) ->
process_subtree(Subtree, Subtree, [], 1).
process_subtree([], _Subtree, Acc, _Index) ->
Acc;
process_subtree([H|T], Subtree, Acc, Index) ->
A = lists:nth(1,H),
Bind = length( Subtree ) - Index + 1,
B = lists:last( lists:nth( Bind, Subtree) ),
% generating the possibilities of grammar
Pos = [ list_to_binary(binary:bin_to_list(X)++" "++binary:bin_to_list(Y)) || X<-A, Y<-B ],
% looking up in the grammar
Result = lists:flatten( [ ets:match(cyk, {'$1', X}) || X <- Pos ] ),
process_subtree(T, Subtree, Acc++Result, Index + 1).
%% Extract a subtree from the representation
extract_subtree(Representation, Position) ->
Size = length(Representation) + 1,
extract_subtree(Representation, Size, Position, []).
extract_subtree([], _Size, _Position, Acc) ->
lists:reverse(Acc);
extract_subtree([H|T], Size, Position, Acc) ->
Segment = lists:sublist(H, Position, Size),
extract_subtree(T, Size - 1, Position, [Segment|Acc]).
%%------------------------------------------
%%
%% Test
%% using the same example as
%% http://en.wikipedia.org/wiki/CYK_algorithm
%%
%%------------------------------------------
test_analyze() ->
init_storage(),
import_grammar_file("grammar.txt"),
analyze("she eats a fish with a fork").
语法文件(grammar.txt)
S -> NP VP
VP -> VP PP
VP -> V NP
VP -> eats
PP -> P NP
NP -> Det N
NP -> she
V -> eats
P -> with
N -> fish
N -> fork
Det -> a
可以从 erlang shell 测试代码
> c(cyk).
> cyk:test_analyze().
parsing <<"S">> -> <<"NP VP">>
parsing <<"VP">> -> <<"VP PP">>
parsing <<"VP">> -> <<"V NP">>
parsing <<"VP">> -> <<"eats">>
parsing <<"PP">> -> <<"P NP">>
parsing <<"NP">> -> <<"Det N">>
parsing <<"NP">> -> <<"she">>
parsing <<"V">> -> <<"eats">>
parsing <<"P">> -> <<"with">>
parsing <<"N">> -> <<"fish">>
parsing <<"N">> -> <<"fork">>
parsing <<"Det">> -> <<"a">>
Grammar file imported
analysing: "she eats a fish with a fork"
wordlist: [<<"she">>,<<"eats">>,<<"a">>,<<"fish">>,<<"with">>,<<"a">>,
<<"fork">>]
representation: [[<<"NP">>],
[<<"VP">>,<<"V">>],
[<<"Det">>],
[<<"N">>],
[<<"P">>],
[<<"Det">>],
[<<"N">>]]
result: [[[<<"S">>]],
[[],[<<"VP">>]],
[[],[],[]],
[[<<"S">>],[],[],[]],
[[],[<<"VP">>],[],[],[<<"PP">>]],
[[<<"S">>],[],[<<"NP">>],[],[],[<<"NP">>]],
[[<<"NP">>],
[<<"VP">>,<<"V">>],
[<<"Det">>],
[<<"N">>],
[<<"P">>],
[<<"Det">>],
[<<"N">>]]]
对于这个例子来说,代码似乎工作得很好,但我一直在寻找改进它的方法(让它更像erlang),特别是让处理分布在多个进程/节点上。
我想每个步骤的所有 process_subtree 执行都可以并发完成,但我真的不知道如何实现。
如有任何建议,我们将不胜感激!
最佳答案
我编写了这个使用并发执行的解决方案。
与 Eric 的解决方案相比,多进程的使用需要一些更改,一些更改是因为我认为它更有效(我恢复了规则集中的键和值,并且我选择了一组),一些是因为我认为它更干净(我在打开它的函数中关闭了语法文件),还有一些是因为我更熟悉这些模块(string:tokens ...)。
[编辑]
我通过更快的递归调用替换了无用的生成,并通过添加一条消息来同步进程来抑制等待函数。
我通过查看 CYK 算法的 Javascript 动画中的精美动画得到了实现此实现的想法,但遗憾的是该动画已不再可用。
@Eric,可以使用观察者打开 ets 分析来查看分析的所有步骤,这就是我不删除它的原因。
-module(cyk).
-export([
import_grammar_file/1,
add_grammar_rule/2,
analyze/1,
test_analyze/1,
test_analyze/0
]).
%%------------------------------------------
%%
%% Grammar
%%
%%------------------------------------------
%% Import a grammar file
import_grammar_file(File) ->
reset_ets(rules, ets:info(rules)),
{ok, Device} = file:open(File, read),
ok = add_grammar_rule(Device,file:read_line(Device)),
file:close(Device),
io:format("Grammar file imported~n").
%% Add a grammar rule
add_grammar_rule(_,eof) -> ok;
add_grammar_rule(Device,{ok,Rule}) ->
[T,"->",H|Q] = string:tokens(Rule," \n"),
Key = key(H,Q),
insert(Key,T,ets:lookup(rules, Key)),
add_grammar_rule(Device,file:read_line(Device)).
key(H,[]) -> H;
key(H,[Q]) -> {H,Q}.
insert(Key,T,[]) -> ets:insert(rules, {Key,[T]});
insert(Key,T,[{Key,L}]) -> ets:insert(rules, {Key,[T|L]}).
%%------------------------------------------
%%
%% Main logic
%%
%%------------------------------------------
%% Analyze a sentence
analyze(Sentence) ->
reset_ets(analyze, ets:info(analyze)),
io:format("analysing: ~p~n", [Sentence]),
WordList = string:tokens(Sentence, " "),
Len = length(WordList),
Me = self(),
lists:foldl(fun(X,{J,Pid}) -> ets:insert(analyze,{{0,J},ets:lookup_element(rules,X,2)}),
(NewPid = spawn(fun() -> whatis(1,J,Len,Pid,Me) end)) ! {done,0},
{J+1,NewPid} end,
{1,none}, WordList),
receive
M -> M
end.
reset_ets(Name, undefined) -> ets:new(Name,[set, named_table,public]);
reset_ets(Name, _) -> ets:delete_all_objects(Name).
whatis(Len,1,Len,_,PidRet) -> PidRet ! ets:lookup_element(analyze,{Len-1,1},2); % finished
whatis(I,J,Len,_,_) when I + J == Len +1 -> ok; % ends useless processes
whatis(I,J,Len,Pid,PidRet) ->
receive {done,V} when V == I-1 -> ok end,
Cases = lists:map(fun({X,Y}) -> [{A,B} || A <- ets:lookup_element(analyze,X,2),
B <- ets:lookup_element(analyze,Y,2)] end,
[{{X-1,J},{I-X,J+X}} || X <- lists:seq(1,I)]),
Val = lists:foldl(fun(X,Acc) -> case ets:lookup(rules,X) of
[] -> Acc;
[{_,[R]}] -> [R|Acc]
end end,
[],lists:flatten(Cases)),
ets:insert(analyze,{{I,J},Val}),
send(Pid,I),
whatis(I+1,J,Len,Pid,PidRet).
send(none,_) -> ok;
send(Pid,I) -> Pid ! {done,I}.
%%------------------------------------------
%%
%% Test
%% using the same example as
%% http://en.wikipedia.org/wiki/CYK_algorithm
%%
%%------------------------------------------
test_analyze(S) ->
import_grammar_file("grammar.txt"),
analyze(S).
test_analyze() ->
test_analyze("she eats a fish with a fork").
关于erlang - Erlang中CYK算法实现的代码审查,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23392576/
我正在开发一个名为 Quiz 的系统... 最后剩下的就是“线索”。目前我有 我想从 xml 中删除线索,因为很难
一旦拉取请求被批准,如果还有进一步的提交: 拉取请求应该转到 未获批准 自动状态。 这能做到吗? 最佳答案 能力推送新提交时取消过时的拉取请求批准 是 下的设置合并前需要拉取请求审查 在 branch
我想发送我的App进行外部Beta测试,所以我想为此使用Apple的新TestFlight系统。 我设法邀请了内部测试人员,他们可以测试该应用程序,因此我发现我必须将该应用程序提交给外部Beta测试。
对于以某种方式使这个 if 条件更短(更优雅),你有什么建议吗? if (@path.start_with? "scp" || @path.start_with? "http") @source
我管理一个在线目录。目前,内部人员手动更新,他们的更改立即可见。现在我们要添加一个验证步骤:Tom 进行更改,Jerry 批准。 我看到两条路,但都不优雅。 保留整个数据库的第二个“工作副本”。 在同
我的程序应该采用任意数量的单字文本字符串参数,每个参数的长度小于 128 个字符。它将所有文本从 stdin 复制到 stdout,但输入中看到的任何单词都会被单词 CENSORED 替换。到目前为止
我有一个团队在几个 GitHub 存储库中工作。每个存储库都有负责人(维护者)对拉取请求进行最终审查,如果可以则将其合并到 master 中。所有其他成员都是此存储库的开发人员和审阅者(但可能在另一个
是否有任何官方/有效的方式来发送对 Android 开发者指南的反馈?我注意到一个错误(一个页面建议使用文档中列为已弃用的方法)并且想知道是否有办法向网站上的工作人员指出它,但我找不到任何东西。 最佳
按照目前的情况,这个问题不适合我们的问答形式。我们希望答案得到事实、引用或专业知识的支持,但这个问题可能会引发辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开,visit the
(来源:azureedge.net) 我的代码存储库位于 GitHub 中,我的管道在 Azure DevOps 中配置。 我需要让 Azure DevOps 检查和过滤提交到我的 GitHub 存储
我想编写一个函数,从列表中删除尾随的 nil。我首先尝试用递归优雅地写它,但结果是这样的: (defun strip-tail (lst) (let ((last-item-pos (positi
我在 git review 上得到以下内容: git review You are about to submit multiple commits. This is expected if you
我正在使用 Apple iTunes Connect 网站。我希望我的 iPhone friend 可以通过 testflight 安装我的应用程序。我的 friend 不属于我的工作团队,因此他没有
就目前而言,这个问题不适合我们的问答形式。我们希望答案得到事实、引用资料或专业知识的支持,但这个问题可能会引发辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开,visit the
我在 visual studio 2010 中使用 git 进行源代码控制。我可以使用诸如“git status”、“git commit”之类的命令,但是当我尝试使用“git review”时,我得
我是一名优秀的程序员,十分优秀!