複数のテキスト ファイル ドキュメント間の類似性を計算するために、次のアプローチを採用しています。
- 特定のディレクトリ内のドキュメントごとに、ドキュメントをチャンク (基本的なスライディング ウィンドウ アルゴリズムから計算された長いバイト シーケンス) に分割します。
- 各チャンクのフィンガープリントを計算します。つまり、MD5 などのハッシュ アルゴリズムを使用してチャンクをハッシュします。
- 異なるファイルで発生するチャンクを比較する
ここまでで、最初の 2 つのステップを実装しました。Google Guava の MultiMap を使用して、ハッシュされたチャンクをファイル名に関連付けています。ステップ3に関しては、私は今次のことをしようとしています:
For each file {
get the file's hashed chunks
compare the hashed chunks with those of every other file
}
ここでの考え方は、共通のエントリのファイル シグネチャを比較し、シグネチャの共通部分が特定の類似度しきい値を超えているファイルのクラスタのみを報告することです。しかし、最終的には、このロジックを微調整して、ソース ファイルと比較した各ファイルの類似性スコアを取得したいと考えています。
私の質問:ステップ 3 でハッシュ化されたチャンクを比較する最良の方法は何ですか? また、前者との類似性の概念をどのように組み込むことができますか? これまでの私のコードは次のとおりです。
public class ContentBasedChunkingMain implements Similarity {
Multimap<String, byte[]> hashMap = ArrayListMultimap.create();
public ContentBasedChunkingMain() {
}
@Override
public void getSimilarity(String dir) {
// Document directory
File directory = new File(dir);
Collection<File> collection = FileUtils.listFiles(directory,
TrueFileFilter.INSTANCE, TrueFileFilter.INSTANCE);
ArrayList<File> files = new ArrayList<File>(Arrays.asList(collection
.toArray(new File[0])));
// For each file in the directory
for (File f : files) {
// Get chunks
ArrayList<String> chunks = Chunker.getChunks(f);
for (String s : sentences) {
// MD5 Hash each sentence
MD5HashFunction h = new MD5HashFunction();
System.out.println(h.byteToHex(h.hash(s)));
// Store filename and hashed chunk into MultiMap
hashMap.put(f.getAbsolutePath(), h.hash(s));
}
}
// Step 3
for (File f : files) {
// for each file, get the file's hashed chunks
Collection<byte[]> bytes = hashMap.get(f.getAbsolutePath());
// compare ...
}
}
私が従うアルゴリズム、Content-Based Chunking Algorithm については、次の論文で詳しく説明されています。
http://www.hpl.hp.com/techreports/2009/HPL-2009-90.pdf