The "Text-Levenshtein" solution seems like it might work

Whilst Levenshtein will work for your application, it is an exhaustive, and thus very slow O(n*m) algorithm.

Even the XS version is many times slower than the xor method you use in the OP. As such, it is best avoided unless no other short-circuiting method can be found to solve your problem.

The good news is that alternatives are nearly always possible. The only thing lacking here is a clear description of your data.

If you would step back from your jargon and conceptual visualisation of the problem; and answer the multiple, impassioned pleas asking "what does your actual data look like?"; then I'm pretty sure you would have multiple, efficient, working solutions by now.