LCS in Python

One way to do all or nothing comparison is with hashes. Hashes can be stored, used remotely, etc.

Hashes have use in security (where the hash algorithm should be very discriminating and slow) and in file comparisons (where the hash algorithm should be discriminating and fast). Here is the Python code [#1]

import hashlib
textList1 = [
	"Myrtle Beach",
	"Myrtle Beech",
	"Myrtle Beach"
	]
for pos1,text1 in enumerate(textList1):
	for pos2,text2 in enumerate(textList1):
		if pos2 > pos1:
			print("Compare:")
			print("\t{0:d}. \"{1:s}\"".format(pos1,text1))
			print("\t{0:d}. \"{1:s}\"".format(pos2,text2))
			text1e = text1.encode("utf-8")
			text2e = text2.encode("utf-8")
			for type1 in ["md4", "md5", "sha1"]:
				m1 = hashlib.new(type1)
				m1.update(text1e)
				hex1 = m1.hexdigest()
				m2 = hashlib.new(type1)
				m2.update(text2e)
				hex2 = m2.hexdigest()
				if hex1 == hex2:
					print("\t\t{0:s}: (same)".format(type1))
				else:
					print("\t\t{0:s}: (different)".format(type1))
				print("\t\t\t{0:s}".format(hex1))
				print("\t\t\t{0:s}".format(hex2))

Here is the output of the Python code.

Compare:
	0. "Myrtle Beach"
	1. "Myrtle Beech"
		md4: (different)
			48e1ae664d742c55b9bd52ce33dea1fa
			5abdb64be305dcea4fb85118f01f7306
		md5: (different)
			4edee97902d5ac7a636e86391f4ef96a
			cc9e9c64e8b1e841fca367480429e4e8
		sha1: (different)
			45079f31d307dc2ab244549841e8a6342bff15e9
			066a948ccbffbbf198cb4a10154423db72995c47
Compare:
	0. "Myrtle Beach"
	2. "Myrtle Beach"
		md4: (same)
			48e1ae664d742c55b9bd52ce33dea1fa
			48e1ae664d742c55b9bd52ce33dea1fa
		md5: (same)
			4edee97902d5ac7a636e86391f4ef96a
			4edee97902d5ac7a636e86391f4ef96a
		sha1: (same)
			45079f31d307dc2ab244549841e8a6342bff15e9
			45079f31d307dc2ab244549841e8a6342bff15e9
Compare:
	1. "Myrtle Beech"
	2. "Myrtle Beach"
		md4: (different)
			5abdb64be305dcea4fb85118f01f7306
			48e1ae664d742c55b9bd52ce33dea1fa
		md5: (different)
			cc9e9c64e8b1e841fca367480429e4e8
			4edee97902d5ac7a636e86391f4ef96a
		sha1: (different)
			066a948ccbffbbf198cb4a10154423db72995c47
			45079f31d307dc2ab244549841e8a6342bff15e9

The example shows just small strings which would be easy to compare via text comparison.

What happens when the text is the text of a huge file?

And what if the files are separated and on different computers (e.g., in a web update). Only the hashes need to be transferred and managed remotely, not the entire files. Same for cluster computing where files may be on different computers.

In many cases, a yes or no answer is not sufficient. One desires to know the similarities and differences of a file.

One example is the percent match of one file with another.

Consider 10,000 files to be compared with 10,000 files, each with about 1,000 lines.

10,000 * 10,000 = 100,000,000 file. comparisons each with 1,000 *1,000 = 1,000,000 line comparisons.

Since each pair of file comparisons can be assumed independent of the others, cluster computing starts to look promising.

A start is to compare one file with another file for similarities and differences.

The difflib package, part of the Python installation, can be used for various aspects of the LCS (Longest Common Subsequence) problem.

Here is the Python code [#2]

import difflib
a1 = "nematode-knowledge"
b1 = "empty-bottle"
print("Left: \"{0:s}\"".format(a1))
print("Right: \"{0:s}\"".format(b1))
print("Changes:")
sequence1 = difflib.SequenceMatcher(None,a1,b1,autojunk=False)
lcsList1 = []
for op1,i1,i2,j1,j2 in sequence1.get_opcodes():
	a2 = a1[i1:i2]
	b2 = b1[j1:j2]
	if op1 == "insert":
		print("\t{0:s} [{1:s}]".format(op1,b2))
	elif op1 == "delete":
		print("\t{0:s} [{1:s}]".format(op1,a2))
	elif op1 == "replace":
		print("\t{0:s} [{1:s}] with [{2:s}]".format(op1,a2,b2))
	else:
		print("\t{0:s} [{1:s}]".format(op1,a2))
		lcsList1.append(a2)
lcsText1 = "".join(lcsList1)
print("LCS: {0:s}".format(lcsText1))

Here is the output of the Python code.

Left: "nematode-knowledge"
Right: "empty-bottle"
Changes:
	delete [n]
	equal [em]
	replace [a] with [p]
	equal [t]
	insert [y-b]
	equal [o]
	replace [de-know] with [tt]
	equal [le]
	delete [dge]
LCS: emtole