Hello,
I hope this is the right category for this question. It's my first time posting.
I have a programming problem where I'm matching up words from two different sources (in my case, two Greek New Testament sources), for example:
"he then lifted armour then ran"
"then he lifted armor ran"
For each word of the first line, I need to determine which word (if any) of the second line is the best match. In order to do this, I write a function that compares strings and evaluates match quality, and then generates a matrix of these qualities:
The problem now is to select the matches to maximize their sum, and I need an algorithm to choose the best matches from among the matrix. Because each match is a unique one-to-one mapping, the constraint is that only one element per row and column can be chosen. Inspecting the matrix you can see that the best choice in this trivial case is to select the numbers in bold, which results in 500, but is there an algorithm that can find the best match? A deductive algorithm would be great but approximate methods or strategies are ok too. I'd be surprised if this doesn't already fall into a class of math problems.
My matrices are up to 30x30, so I can't do a brute force solution (going through 30! possibilities) unless you have a quantum computer
. If you think your algorithm works but can't prove it, suggest it and I can test it against a brute-force method on smaller matrices.
Thanks,
Rich K
I hope this is the right category for this question. It's my first time posting.
I have a programming problem where I'm matching up words from two different sources (in my case, two Greek New Testament sources), for example:
"he then lifted armour then ran"
"then he lifted armor ran"
For each word of the first line, I need to determine which word (if any) of the second line is the best match. In order to do this, I write a function that compares strings and evaluates match quality, and then generates a matrix of these qualities:
| then | he | lifted | armor | ran | |
| he | 20 | 100 | 10 | 0 | 0 |
| then | 100 | 20 | 2 | 30 | 0 |
| lifted | 2 | 10 | 100 | 0 | 0 |
| armour | 0 | 0 | 0 | 100 | 20 |
| then | 80 | 20 | 2 | 30 | 0 |
| ran | 0 | 0 | 0 | 19 | 100 |
The problem now is to select the matches to maximize their sum, and I need an algorithm to choose the best matches from among the matrix. Because each match is a unique one-to-one mapping, the constraint is that only one element per row and column can be chosen. Inspecting the matrix you can see that the best choice in this trivial case is to select the numbers in bold, which results in 500, but is there an algorithm that can find the best match? A deductive algorithm would be great but approximate methods or strategies are ok too. I'd be surprised if this doesn't already fall into a class of math problems.
My matrices are up to 30x30, so I can't do a brute force solution (going through 30! possibilities) unless you have a quantum computer
. If you think your algorithm works but can't prove it, suggest it and I can test it against a brute-force method on smaller matrices.Thanks,
Rich K