Enhancing a Genetic Algorithm with a Solution Archive to Reconstruct Cross Cut Shredded Text Documents
Enhancing a Genetic Algorithm with a Solution Archive to Reconstruct Cross Cut Shredded Text Documents
复制标题
使用解决方案存档增强遗传算法来重建横切切碎的文本文档
DOI：
10.1007/978-3-642-53856-8_48
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
G. Raidl
中科院分区：
文献类型：
--
作者：
Benjamin Biesinger;Christian Schauer;Bin Hu;G. Raidl
在这项工作中，一个trie为基础的完整的解决方案档案的概念结合遗传算法被应用到重建的横切切碎的文本文件（RCCSTD）的问题。此存档能够检测并随后将重复转换为新的尚未访问的解决方案。横切碎文件是指被切成相同大小和形状的矩形片的文件。文件的重建在法医学中具有很高的意义。比较了索引trie和链接trie作为底层数据结构的两种类型。实验表明，后者需要相当少的内存，而不影响运行时间。虽然存档增强的遗传算法产生更好的结果，运行与固定次数的迭代，优势减少，由于额外的开销时，考虑运行时间。
In this work the concept of a trie-based complete solution archive in combination with a genetic algorithm is applied to the Reconstruction of Cross-Cut Shredded Text Documents (RCCSTD) problem. This archive is able to detect and subsequently convert duplicates into new yet unvisited solutions. Cross-cut shredded documents are documents that are cut into rectangular pieces of equal size and shape. The reconstruction of documents can be of high interest in forensic science. Two types of tries are compared as underlying data structure, anindexed trieand alinked trie. Experiments indicate that the latter needs considerably less memory without affecting the run-time. While the archive-enhanced genetic algorithm yields better results for runs with a fixed number of iterations, advantages diminish due to the additional overhead when considering run-time.