3

有几条路径，例如：

1: /abc/def/some/common/part/xyz/file1.ext
2: /other/path/to/7433/qwe/some/common/part/anotherfile.ext
3: /misc/path/7433/qwe/some/common/part/filexx.ext
4: /2443/totally/different/path/file9988.ext
5: /abc/another/same/path/to/ppp/thisfile.ext
6: /deep1/deep2/another/same/path/to/diffone/filename.ext

我需要找到共同的部分 - 每个可能的部分，例如。如果可能的话，在上面找到共同的部分：

 /some/common/part/ - in the paths 1,2,3
 /another/same/path/to/ - in the 5,6
 /path/to/ - in the 2,5,6
 /path/ - 2,3,4,5,6

ETC..

我根本不知道如何解决这个问题 - 什么方法是好的

  • 基于字符串 -在某种程度上找到字符串的共同部分
  • 基于列表 - 将所有路径拆分为列表并在某种程度上比较常见元素的数组
  • 树图 -有点找到图的共同部分
  • 其他？

当我得到一些解决这个问题的方向时，我（可能）能够自己编写代码- 所以不想要免费的编程服务- 但需要一些指导如何开始。

我确定这里已经有一些 CPAN 模块可以帮助我，但我真的不知道如何从 30k 模块列表中找到适合上述问题的正确有用模块。:(

编辑 - 我需要这个：

拥有约。200k 个文件，位于 10k 个目录中，其中许多“属于一起”，例如：

/u/some/path/project1/subprojct/file1
/u/backup/of/work/date/project1/subproject/file2
/u/backup_of_backup/of/work/date/project1/subproject/file2
/u/new/addtions/to/projec1/subproject/file3

这些文件是不同类型的（pdf、图像、doc、txt 等），有几个是相同的（如上面的 file2 - 易于使用 Digest::MD5 过滤），但“将它们组合在一起”的唯一方法是基于“common路径的“部分” - 例如“project1/subproject”等等..

另一个文件具有相同的 MD5，因此可以过滤掉重复项，但它们位于不同的树中，例如

/u/path/some/file
/u/path/lastest_project/menu/file
/u/path/jquery/menu/file
/u/path/example/solution/jquery/menu/file

因此，文件是相同的（相同的 md5），但需要将一个副本移动到正确的位置（并删除其他文件），并且需要在一定程度上确定“最常用”的公共路径，并收集标签......（旧路径元素是标签）

背后的想法是：

  • 如果相同的 md5 文件大多存储在某个公共路径下- 我可以决定将一份副本移动到哪里......

而且它更复杂，但上面的解释就足够了；）

只需要降低我的硬盘上的熵；）

4

2 回答 2

2

在这个线程中有一些关于找到最长的公共连续子串的讨论：http ://www.nntp.perl.org/group/perl.fwp/2002/02/msg1662.html

“赢家”似乎是以下代码，但您可以尝试其他一些事情：

#!/usr/bin/perl
use strict;
use warnings;

sub lcs {

    my $this = shift;
    my $that = shift;

    my $str = join "\0", $this, $that;
    my $len = 1;
    my $lcs;
    while ($str =~ m{ ([^\0]{$len,}) (?= [^\0]* \0 [^\0]*? \1 ) }xg) {
        $lcs = $1;
        $len = 1 + length($1);
    }

    if ($len == 1) { print("No common substring\n"); }
    else {
        print("Longest common substring of length $len: \"");
        print("$lcs");
        print("\"\n");
    }
}

请记住，您必须对其进行一些调整以考虑到您只想要匹配的整个子目录的事实......即，更改if ($len == 1)为类似if ($len == 1 or $lcs !~ /^\// or $lcs !~ /\/$/)

您还必须添加一些簿记以跟踪哪些匹配。当我在上面的示例中运行此代码时，它还/abc/在第 1 行和第 5 行中找到了匹配项。

可能有问题也可能没有问题的一件事是以下两行：

/abc/another/same/path/to/ppp/thisfile.ext
/abc/another/different/path/to/ppp/otherfile.ext

将匹配：

/abc/another/

但不在：

/path/to/ppp/

但是 -这是坏消息- 您将不得不与 n=200,000 个文件进行 O(n^2) 比较。这可能需要大量的时间。

另一种解决方案是遍历列表中的每个路径，将其所有可能的目录路径作为键添加到哈希中，并将文件本身推送到哈希中（以便该值是包含此路径的文件数组） . 像这样的东西：

use strict;
use warnings;
my %links;

open my $fh, "<", 'filename' or die "Can't open $!";
while (my $line = <$fh>) {
    chomp($line);
    my @dirs = split /\//, $line;
    for my $i (0..$#dirs) {
        if ($i == $#dirs) {
            push(@{ $links{$dirs[$i]} }, $line);
        }
        for my $j ($i+1..$#dirs) {
            push(@{ $links{join("/",@dirs[$i..$j])} }, $line);
            #PROCESS THIS if length of array is > 1
        }
    }
}

当然，这会占用大量的内存。有 200,000 个文件要处理，无论您尝试什么都可能会遇到困难，但也许您可以将其分解成更易于管理的块。希望这将为您提供一个起点。

于 2013-06-30T10:14:53.770 回答
2

要解决这个问题，您需要正确的数据结构。计算部分路径的哈希效果很好：

use File::Spec;

my %Count_of = ();

while( <DATA> ){
  my @names = File::Spec->splitdir( $_ );

  # remove file
  pop @names;

  # if absolute path, remove empty names at start
  shift @names while length( $names[0] ) == 0;

  # don't count blank lines
  next unless @names;

  # move two cursor thru the names,
  # and count the partial parts
  # created from one to the other
  for my $i ( 0 .. $#names ){
    for my $j ( $i .. $#names ){
      my $partial_path = File::Spec->catdir( @names[ $i .. $j ] );
      $Count_of{ $partial_path } ++;
    }
  }
}

# now display the results
for my $path ( sort { $Count_of{$b} <=> $Count_of{$a} || $a cmp $b } keys %Count_of ){

  # skip if singleton.
  next if $Count_of{ $path } <= 1;

  printf "%3d : %s\n", $Count_of{ $path }, $path;
}


__DATA__
/abc/def/some/common/part/xyz/file1.ext
/other/path/to/7433/qwe/some/common/part/anotherfile.ext
/misc/path/7433/qwe/some/common/part/filexx.ext
/2443/totally/different/path/file9988.ext
/abc/another/same/path/to/ppp/thisfile.ext
/deep1/deep2/another/same/path/to/diffone/filename.ext
于 2013-06-30T14:26:42.063 回答