Finding and Renaming Mislabeled Duplicates

I inadvertently formatted a Time Machine backup external hard drive. I was able to recover many of the files, but not the names of those files.

All of the recovered files have generic names like “file01010101.doc”, which is not helpful. In order to know which files are duplicates, I need to compare the recovered files the originals I have on my machine, and have them renamed accordingly. Then, any files that still have a generic name must be unique and not a duplicate.

Question: How do I do this automatically? Is there a program, bash script, or Automator action that can do duplicate file finding and renaming? There’s almost 500,000 files, so doing this manually is not practical.