我是Perl的新手.我需要解析一个制表符分隔的文本文件.例如:
From name To name Timestamp Interaction
a b Dec 2 06:40:23 IST 2000 comment
c d Dec 1 10:40:23 IST 2001 like
e a Dec 1 16:03:01 IST 2000 follow
b c Dec 2 07:50:29 IST 2002 share
a c Dec 2 08:50:29 IST 2001 comment
c a Dec 11 12:40:23 IST 2008 like
e c Dec 2 07:50:29 IST 2000 like
c b Dec 11 12:40:23 IST 2008 follow
b a Dec 2 08:50:29 IST 2001 share
解析后,我需要根据用户交互创建组.在这个例子中
a<->b
b<->a
c<->a
a<->c
b<->c
c<->b
为此,我们可以创建一个组.我们需要显示组列表.我需要一些关于如何解析文件和表单组的指针？
编辑 约束 - >创建组至少需要3个用户.交互只不过是两个用户之间进行了一些沟通.哪种沟通无关紧要
我的解决方法是
我们删除用户之间的重复交互.例如"a <> b like"如果"a <> b follow"存在,那么我们删除这一行.
创建存储两个用户交互的二维数组即
To Name a b c d
From Name
a X <> <> X
b <> X <> X
c <> <> X X
d X <> X X
X =表示没有交互<> =表示交互
在这种方法中,我们从第一行开始,即"a"用户检查"b".如果"a"与"b"相互作用,则我们执行反向,即"b"与"a"相互作用.每列执行相同的步骤.
但这种方法取决于用户数量.如果有1000个用户,那么我们必须创建1000 X 1000矩阵.有没有办法解决这个问题
我添加了样本输入
a c Dec 2 06:40:23 IST 2000 comment
f g Dec 2 06:40:23 IST 2009 like
c a Dec 2 06:40:23 IST 2009 like
g h Dec 2 06:40:23 IST 2008 like
a d Dec 2 06:40:23 IST 2008 like
r t Dec 2 06:40:23 IST 2007 share
d a Dec 2 06:40:23 IST 2007 share
t u Dec 2 06:40:23 IST 2006 follow
a e Dec 2 06:40:23 IST 2006 follow
k l Dec 2 06:40:23 IST 2009 like
e a Dec 2 06:40:23 IST 2009 like
j k Dec 2 06:40:23 IST 2003 like
c d Dec 2 06:40:23 IST 2003 like
l j Dec 2 06:40:23 IST 2002 like
d c Dec 2 06:40:23 IST 2002 like
m n Dec 2 06:40:23 IST 2005 like
c e Dec 2 06:40:23 IST 2005 like
m l Dec 2 06:40:23 IST 2011 like
e c Dec 2 06:40:23 IST 2011 like
h j Dec 2 06:40:23 IST 2010 like
d e Dec 2 06:40:23 IST 2010 like
o p Dec 2 06:40:23 IST 2009 like
e d Dec 2 06:40:23 IST 2009 like
p q Dec 2 06:40:23 IST 2000 comment
q p Dec 2 06:40:23 IST 2009 like
a p Dec 2 06:40:23 IST 2008 like
p a Dec 2 06:40:23 IST 2007 share
l p Dec 2 06:40:23 IST 2003 like
j l Dec 2 06:40:23 IST 2002 like
t r Dec 2 06:40:23 IST 2000 comment
r h Dec 2 06:40:23 IST 2009 like
j f Dec 2 06:40:23 IST 2008 like
g d Dec 2 06:40:23 IST 2007 share
w q Dec 2 06:40:23 IST 2003 like
o y Dec 2 06:40:23 IST 2002 like
x y Dec 2 06:40:23 IST 2000 comment
y x Dec 2 06:40:23 IST 2009 like
x z Dec 2 06:40:23 IST 2008 like
z x Dec 2 06:40:23 IST 2007 share
y z Dec 2 06:40:23 IST 2003 like
z y Dec 2 06:40:23 IST 2002 like
输出应该是:
(a,c, d, e)
(x,y,z)
解析很容易.只是一个split /\t/可能就足够了.但是,Text :: xSV或Text :: CSV可能会更好.
对于连接,您可以使用Graph模块.为了能够有效地使用该模块,您至少需要了解图论的基础知识.
请注意,强连接组件定义为:
如果存在从图中的每个顶点到每个其他顶点的路径,则有向图称为强连接.特别是,这意味着每个方向的路径; 从路径
a到b,也从一个路径b来a.有向图G的强连通分量是其最大强连通子图.
但是,请注意,如果您拥有a <-> b和b <-> c,a和b,并且c将形成一个强连接组件,这意味着要求的组合比两个方向上彼此交互的组的所有成员要弱.
我们仍然可以使用它来减少搜索空间.获得候选组后,您可以检查每个候选组,看它是否适合您对组的定义.如果候选组不符合您的要求,那么您可以检查所有子集少一个成员.如果在这些组中没有找到任何组,则可以查看具有两个较少成员的所有子集,依此类推,直到达到最小组大小限制.
下面的脚本使用了这个想法.但是,它很可能不会扩展.我强烈怀疑有人可能会把一些SQL魔法放在一起,但我的思想太过限制了.
#!/usr/bin/env perl
use strict;
use warnings;
use Graph;
use Algorithm::ChooseSubsets;
use constant MIN_SIZE => 3;
my $interactions = Graph->new(
directed => 1,
);
while (my $interaction = <DATA>) {
last unless $interaction =~ /\S/;
my ($from, $to) = split ' ', $interaction, 3;
$interactions->add_edge($from, $to);
}
my @groups = map {
is_group($interactions, $_) ? $_
: check_subsets($interactions, $_)
} grep @$_ >= MIN_SIZE, $interactions->strongly_connected_components;
print "Groups: \n";
print "[ @$_ ]\n" for @groups;
sub check_subsets {
my ($graph, $candidate) = @_;
my @groups;
for my $size (reverse MIN_SIZE .. (@$candidate - 1)) {
my $subsets = Algorithm::ChooseSubsets->new(
set => $candidate,
size => $size,
);
my $groups_found;
while (my $subset = $subsets->next) {
if (is_group($interactions, $subset)) {
++$groups_found;
push @groups, $subset;
}
}
last if $groups_found;
}
return @groups;
}
sub is_group {
my ($graph, $candidate) = @_;
for my $member (@$candidate) {
for my $other (@$candidate) {
next if $member eq $other;
return unless $graph->has_edge($member, $other);
return unless $graph->has_edge($other, $member);
}
}
return 1;
}
__DATA__
a c Dec 2 06:40:23 IST 2000 comment
f g Dec 2 06:40:23 IST 2009 like
c a Dec 2 06:40:23 IST 2009 like
g h Dec 2 06:40:23 IST 2008 like
a d Dec 2 06:40:23 IST 2008 like
r t Dec 2 06:40:23 IST 2007 share
d a Dec 2 06:40:23 IST 2007 share
t u Dec 2 06:40:23 IST 2006 follow
a e Dec 2 06:40:23 IST 2006 follow
k l Dec 2 06:40:23 IST 2009 like
e a Dec 2 06:40:23 IST 2009 like
j k Dec 2 06:40:23 IST 2003 like
c d Dec 2 06:40:23 IST 2003 like
l j Dec 2 06:40:23 IST 2002 like
d c Dec 2 06:40:23 IST 2002 like
m n Dec 2 06:40:23 IST 2005 like
c e Dec 2 06:40:23 IST 2005 like
m l Dec 2 06:40:23 IST 2011 like
e c Dec 2 06:40:23 IST 2011 like
h j Dec 2 06:40:23 IST 2010 like
d e Dec 2 06:40:23 IST 2010 like
o p Dec 2 06:40:23 IST 2009 like
e d Dec 2 06:40:23 IST 2009 like
p q Dec 2 06:40:23 IST 2000 comment
q p Dec 2 06:40:23 IST 2009 like
a p Dec 2 06:40:23 IST 2008 like
p a Dec 2 06:40:23 IST 2007 share
l p Dec 2 06:40:23 IST 2003 like
j l Dec 2 06:40:23 IST 2002 like
t r Dec 2 06:40:23 IST 2000 comment
r h Dec 2 06:40:23 IST 2009 like
j f Dec 2 06:40:23 IST 2008 like
g d Dec 2 06:40:23 IST 2007 share
w q Dec 2 06:40:23 IST 2003 like
o y Dec 2 06:40:23 IST 2002 like
x y Dec 2 06:40:23 IST 2000 comment
y x Dec 2 06:40:23 IST 2009 like
x z Dec 2 06:40:23 IST 2008 like
z x Dec 2 06:40:23 IST 2007 share
y z Dec 2 06:40:23 IST 2003 like
z y Dec 2 06:40:23 IST 2002 like
输出:
Groups: [ y z x ] [ e d a c ]