1
\$\begingroup\$

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)
```
\$\endgroup\$
1
1
\$\begingroup\$

This approach will work, but be slow. You will be comparing something like N**2.5 lines in the worst case, which is quite bad. You should be running in something more like linear time.

The biggest problem I see here is that your problem is not well-defined, so first clarify your problem to yourself. What do you want to count as "duplicate text"? Do you want to find the biggest duplicate block? All blocks above a certain size? Do you care if you split a large block into two, or is it important to have the longest possible as one unit? Do you care about matching duplicated text generally or only matching lines? Depending on your problem, the fastest way to do it varies radically.

Then, reduce the number of line comparisons for whatever your problem is. I suggest learning about longest repeated substring (as suggested), and maybe suffix trees.

If you want to squeeze the last ounce of performance out of something line-based, you can try pre-processing by hashing the lines into integers.

\$\endgroup\$
3
  • \$\begingroup\$ The use case is to detect and remove repeating blocks of text, starting with biggest multiline blocks and then down to single lines. To be more specific, I had a bunch of vCard files which had certain fields duplicated and repeated multiple times, sometimes multilines, so I had to make sure that I first remove the bigger blocks before starting removing single line dupes. \$\endgroup\$
    – ccpizza
    Aug 28 at 13:55
  • \$\begingroup\$ Yes, I understand the intuition already. The problem isn't that you're communicating poorly, if that's you're using fuzzy thinking (which is fine most of the time, but not for algorithms). Try turning it into a formally defined problem, and you'll have better lucking designing or finding an algorithm to fit it. \$\endgroup\$ Aug 29 at 0:06
  • \$\begingroup\$ 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. \$\endgroup\$
    – ccpizza
    Aug 29 at 9:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.