5

1行の文字列で構成される約3,500個のファイルがあります。ファイルのサイズはさまざまです（約200bから1mb）。各ファイルを他のファイルと比較して、2つのファイル間で長さが20文字の共通のサブシーケンスを見つけようとしています。サブシーケンスは、各比較中に2つのファイル間でのみ共通であり、すべてのファイル間で共通ではないことに注意してください。

私はこの問題に少し苦労しました、そして私は専門家ではないので、私は少しアドホックな解決策に行き着きました。itertools.combinationsを使用して、Pythonでリストを作成します。リストの組み合わせは約6,239,278になります。次に、ファイルを一度に2つずつ、 libstreeと呼ばれるCで記述されたサフィックスツリーライブラリのラッパーとして機能するPerlスクリプトに渡します。私はこのタイプの解決策を避けようとしましたが、Pythonで唯一の同等のCサフィックスツリーラッパーがメモリリークに悩まされています。

これが私の問題です。私はそれを計時しました、そして私のマシンでは、ソリューションは25秒で約500の比較を処理します。つまり、タスクを完了するには、約3日間の連続処理が必要になります。そして、20文字ではなく25文字を確認するために、もう一度すべてを行う必要があります。私は自分の快適ゾーンから外れていて、あまり優れたプログラマーではないことに注意してください。したがって、はるかにエレガントな方法があると確信しています。これをする。ここで質問してコードを作成し、このタスクをより速く完了する方法について誰かが提案を持っているかどうかを確認したいと思いました。

Pythonコード：

from itertools import combinations
import glob, subprocess

glist = glob.glob("Data/*.g")
i = 0

for a,b in combinations(glist, 2):
    i += 1
    p = subprocess.Popen(["perl", "suffix_tree.pl", a, b, "20"], shell=False, stdout=subprocess.PIPE)
    p = p.stdout.read()
    a = a.split("/")
    b = b.split("/")
    a = a[1].split(".")
    b = b[1].split(".")
    print str(i) + ":" + str(a[0]) + " --- " + str(b[0])
    if p != "" and len(p) == 20:
        with open("tmp.list", "a") as openf:
            openf.write(a[0] + " " + b[0] + "\n")

Perlコード：

use strict;
use Tree::Suffix;

open FILE, "<$ARGV[0]";
my $a = do { local $/; <FILE> };

open FILE, "<$ARGV[1]";
my $b = do { local $/; <FILE> };

my @g = ($a,$b);

my $st  = Tree::Suffix->new(@g);
my ($c) = $st->lcs($ARGV[2],-1);

print "$c";
4

1 に答える 1

4

Perl を呼び出して C を呼び出すように Python を記述するよりも、Python コードを削除してすべてを Perl で記述した方がよいと確信しています。

ファイルに正確に1行が含まれていることが確実な場合は、次のように書くだけでペアをより簡単に読み取ることができます

my @g = <>;

以下のプログラムは、Python と Perl のコードを組み合わせたものと同じ機能を実行すると思いますが、現在 libstree をインストールできないため、テストできません。

しかし、池上が指摘したように、ファイルのペアごとに最長の共通サブシーケンスを計算して保存し、後でそれらをカテゴリに分類する方がはるかに優れています。サブシーケンスの長さだけなのか、それともサブシーケンスの文字や位置が必要なのか、どのような情報が必要なのかわからないため、これをコーディングすることはしません。

use strict;
use warnings;

use Math::Combinatorics;
use Tree::Suffix;

my @glist = glob "Data/*.g";
my $iterator = Math::Combinatorics->new(count => 2, data => \@glist);

open my $fh, '>', 'tmp.list' or die $!;

my $n = 0;
while (my @pair = $iterator->next_combination) {
  $n++;
  @ARGV = @pair;
  my @g = <>;
  my $tree  = Tree::Suffix->new(@g);
  my $lcs = $tree->lcs;
  @pair = map m|/(.+?)\.|, @pair;
  print "$n: $pair[0] --- $pair[1]\n";
  print $fh, "@pair\n" if $lcs and length $lcs >= 20;
}
于 2012-07-21T16:42:34.833 に答える