A quick and dirty line-based approach for detecting duplicated text blocks.
Did not find any references as to what (deterministic) algorithms are there for detecting duplicated text blocks, so went with the most straightforward way: take the biggest possible text block starting from fist line + 1 to the bottom, keep reducing the block size, and when it's size is less than half of the entire document try to compare the block with the other parts of the document, and then keep reducing the block size by one line and repeat the scanning recursively.
Questions: is there a better/faster and more efficient way? does this approach make sense? how and when would it fail? what I might have missed?
#!/usr/bin/env python3
# Remove multiline duplicated blocks from text files
import argparse
import os
import sys
from pathlib import Path
def remove_duplicate_blocks(lines):
num_lines = len(lines)
for idx_start in range(num_lines):
idx_end = num_lines
for idx in range(idx_end, -1, -1):
if idx_start < idx:
dup_candidate_block = lines[idx_start + 1: idx]
len_dup_block = len(dup_candidate_block)
if len_dup_block and len_dup_block < int(num_lines / 2):
for scan_idx in range(idx):
if ((idx_start + 1) > scan_idx
and dup_candidate_block == lines[scan_idx: scan_idx + len_dup_block]):
if config.verbose:
print(f'FOUND DUPLICATE: {dup_candidate_block}')
lines[idx_start + 1: idx] = []
return remove_duplicate_blocks(lines)
return lines
def traverse_tree(conf):
for f in Path(conf.dir).glob(conf.glob):
print(f)
lines = f.open('r', encoding='utf-8').readlines()
clean_lines = remove_duplicate_blocks(lines)
print(clean_lines)
if not conf.dry_run:
with f.open('w', encoding='utf-8') as fo:
fo.write(''.join(clean_lines))
if __name__ == '__main__':
parser = argparse.ArgumentParser(description='''DESCRIPTION:
Find and remove multiline duplicated text blocks ''',
formatter_class=argparse.RawDescriptionHelpFormatter,
epilog='''USAGE:
{0} -d [root_dir] -g [glob_pattern]
'''.format(os.path.basename(sys.argv[0])))
parser.add_argument('--dir', '-d',
help='folder to search in; by default current folder',
default='.')
parser.add_argument('--glob', '-g',
help='glob pattern, i.e. *.html',
default="*.*")
parser.add_argument('--verbose', '-v',
action='store_true',
help="Print duplicated blocks",
default=False)
parser.add_argument('--dry-run', '-dr',
action='store_true',
help="don't change anything; only print result to stdout",
default=False)
config = parser.parse_args(sys.argv[1:])
traverse_tree(config)
```