3

I'm trying to find a solution for the following problem. I have two sets of files:

  • Folder A has around 400 text files.
  • Folder B has around 20 000 text files total in several subfolders.

Files in folder A are either modified versions of files in folder B or they are parts of files in folder B. When I say "parts", I mean that a file in folder A might contain part of the text of a file in folder B, but not everything.

I want to match those pairs i.e. for each file in folder A I want to find the file or files in folder B that most closely resemble the file in folder A.

For example I would like to have the following kind of report:

File ./A/foo123.txt most closely matches file ./B/bar243.txt with 68% of lines identical.
File ./A/bar306.txt most closely matches file ./B/foo85.txt with 30% of lines identical.

Is there a command line tool that I could use to achieve this result? Or what would be the best way to do this?

  • That sounds like a task which takes a long time - if each pair of two is compared this is O(2), which means the number of comparisons is almost n*n where n is the number of files. – Ned64 Oct 8 at 14:41
  • Related unix.stackexchange.com/questions/1079/… – pLumo Oct 8 at 14:53
  • This could be done with a loop of course. However, I know that there are better options. For example there are plagiat testing programs that compare a small number of files to a large database of previously published work and they don't do it by comparing each pair of files separately. I would be surprised if nobody has written a command line tool for doing that kind of comparison between two folders. – ttsc Oct 8 at 15:12
  • they have a huge databases with a lot of pattern indexing .... this is very specialized and imo far beyond U&L ... – pLumo Oct 8 at 15:15
1

Something like this would work:

for fa in A/*; do

    highest_pm=0

    for fb in B/*; do

    num_identical_lines=$(diff --unchanged-group-format='%<' --old-group-format='' --new-group-format='' --changed-group-format='' "$fa" "$fb" | wc -l)
    num_lines_file_a=$(wc -l < "$fa")

    # save permille of matching lines
    pm=$((1000*num_identical_lines/num_lines_file_a))

    # compare with highest permille
    if [ $pm -gt $highest_pm ]; then
        highest_pm=$pm
        best_match="$fb"
    fi

    done

    # output
    [ $highest_pm -gt 0 ] \
    && printf "File %s best matches File %s with %d %% of identical lines.\n" "$fa" "$best_match" $((highest_pm/10)) \
    || printf "File %s has no match\n" "$fa"

done

The evaluation of num_identical_lines is based on this answer.
The rest is just a loop over the files, some comparison and some output ;-)

Output:

File A/file2 has no match
File A/filea best matches File B/fileb with 50 % of identical lines.
  • Thanks. This seems to work. It's very slow, but if there is no tools with a better algorithm available, this will do the job. There is one thing that I would like to clarify. In my example B does contain subfolders. I found that I can make this work for subfolders by adding shopt -s globstar in the beginning and using for fb in B/**; do. However, it turned out that using globstar that way also matches folders and not just files inside the folders. How could I make this work so that it would loop thrgough all files inside all subfolders of B, but not match the subfolders themselves? – ttsc Oct 19 at 12:24

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.