# Remove duplicated multiline blocks in text

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])))

help='folder to search in; by default current folder',
default='.')

help='glob pattern, i.e. *.html',
default="*.*")

action='store_true',
help="Print duplicated blocks",
default=False)

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)
$$$$


• That's exactly why there was the need to ask the question — I was aware I didn't have a clear understanding of how to approach the task and went with a sloppy fuzzy solution instead; the intent was to find reference points, and the hint regarding the longest repeated substring ` was exactly what I was looking for. Aug 29 at 9:35