Python's re module and genealogy problem

[BrJohan]

For some genealogical purposes I consider using Python's re module.

Rather many names can be spelled in a number of similar ways, and in order to match names even if they are spelled differently, I will build regular expressions, each of which is supposed to match a number of similar names.

I guess that there will be a few hundred such regular expressions covering most popular names.

Now, my problem: Is there a way to decide whether any two - or more - of those regular expressions will match the same string?

Or, stated a little differently:

Can it, for a pair of regular expressions be decided whether at least one string matching both of those regular expressions, can be constructed?

If it is possible to make such a decision, then how? Anyone aware of an algorithm for this?

 

[Robert Kern]

For some genealogical purposes I consider using Python's re module.

Rather many names can be spelled in a number of similar ways, and in order to match names even if they are spelled differently, I will build regular expressions, each of which is supposed to match a number of similar names.

I guess that there will be a few hundred such regular expressions covering most popular names.

Now, my problem: Is there a way to decide whether any two - or more - of those regular expressions will match the same string?

Or, stated a little differently:

Can it, for a pair of regular expressions be decided whether at least one string matching both of those regular expressions, can be constructed?

If it is possible to make such a decision, then how? Anyone aware of an algorithm for this?

And if that isn't the best straight line for the old saying, I don't know what is.

http://en.wikiquote.org/wiki/Jamie_Zawinski

Anyways, to your new problem, yes it's possible. Search for "regular expression intersection" for possible approaches. You will probably have to translate the regular expression to a different formalism or at least a different library to implement this.

Consider just listing out the different possibilities. All of your regexes should be "well-behaved" given the constraints of the domain (tightly bounded, at least). There are tools that help generate matching strings from a Python regex. This will help you QA your regexes, too, to be sure that they match what you expect them to and not match non-names.

https://github.com/asciimoo/exrex

 

[Thomas Rachel]

Am 11.06.2014 14:23 schrieb BrJohan:

Can it, for a pair of regular expressions be decided whether at least one string matching both of those regular expressions, can be constructed?

If it is possible to make such a decision, then how? Anyone aware of an algorithm for this?

Just a feeling-based statement: I don't think that is easily possible.

Every RE can potentially match an infinite number of statements.

Just have a look at

re1 = re.compile('A43.*')
re2 = re.compile('.*[0-9][A-F]')

It can easily seen that the area these REs work on is different; they are orthogonal.

So there is an infinite number of strings these REs match.

Thomas

 

[Mark H Harris]

Anyways, to your new problem, yes it's possible. Search for "regular expression intersection" for possible approaches.

I agree, I would not use a decision (decision tree) but would consider a set of filters from most specific to least specific.

marcus

 

[Michael Torrie]

For some genealogical purposes I consider using Python's re module.

Rather many names can be spelled in a number of similar ways, and in order to match names even if they are spelled differently, I will build regular expressions, each of which is supposed to match a number of similar names.

I guess that there will be a few hundred such regular expressions covering most popular names.

Now, my problem: Is there a way to decide whether any two - or more - of those regular expressions will match the same string?

Or, stated a little differently:

Can it, for a pair of regular expressions be decided whether at least one string matching both of those regular expressions, can be constructed?

If it is possible to make such a decision, then how? Anyone aware of an algorithm for this?

You might want to search for fuzzy matching algorithms. Years ago, there was an algorithm called soundex that would generate fuzzy fingerprints for words that would hide differences in spelling, etc. Unfortunately such an algorithm would be language dependent. The problem you are trying to solve is one of those very hard problems in computers and math.

 

[Nick Cash]

You might want to search for fuzzy matching algorithms. Years ago, there was an algorithm called soundex that would generate fuzzy fingerprints for words that would hide differences in spelling, etc. Unfortunately such an algorithm would be language dependent. The problem you are trying to solve is one of those very hard problems in computers and math.

Soundex is actually not horrible, but it is definitely only for English names. Newer variants of Metaphone (http://en.wikipedia.org/wiki/Metaphone) are significantly better, and support quite a few other languages. Either one would most likely be better than the regex approach.

Side note: if your data happens to be in MySQL then it has a builtin "sounds_like" function that compares strings using soundex.

 

[Simon Ward]

For some genealogical purposes I consider using Python's re module.

Rather many names can be spelled in a number of similar ways, and in order to match names even if they are spelled differently, I will build

regular expressions, each of which is supposed to match a number of similar names.

As has been mentioned, you probably want to look at fuzzy matching algorithms rather than aiming at regular expressions, although a quick search suggests there has been some work on fuzzy matching with regular expressions[1].

Now, my problem: Is there a way to decide whether any two - or more - of those regular expressions will match the same string?

If your regexes are truly regular expressions (see [2]*) then they represent regular languages[3], which are really sets. The intersection of these, is another regular language. If you test the string against this it will also match both original languages.

(*this only mentions back references, but I think the look-ahead/behind assertions are also non-regular)

[1]: http://laurikari.net/tre/about/
[2]: https://en.wikipedia.org/wiki/Regular_expression#Patterns_for_non-regular_languages [3]: https://en.wikipedia.org/wiki/Regular_language

Simon

 

[Vlastimil Brom]

For some genealogical purposes I consider using Python's re module.
...

Now, my problem: Is there a way to decide whether any two - or more - of those regular expressions will match the same string?

Or, stated a little differently:

Can it, for a pair of regular expressions be decided whether at least one string matching both of those regular expressions, can be constructed?

Hi,
i guess, you could reuse some available generators for strings matching a given regular expression, see e.g.:
http://stackoverflow.com/questions/492716/reversing-a-regular-expression-in-python/ for example a pyparsing recipe:
http://stackoverflow.com/questions/492716/reversing-a-regular-expression-in-python/5006339#5006339

which might be general enough for your needs - of course, you cannot use unbound quantifiers, backreferences, etc.

Then you can test for identical strings in the generated outputs - e.g. using the set(...) and its intersection method.

You might also check a much more powerful regex library https://pypi.python.org/pypi/regex

which, beyond other features, also supports the mentioned fuzzy matches, cf.

regex.findall(r"\bSm(?:ith){e<3}\b", "Smith Smithe Smyth Smythe Smijth") ['Smith', 'Smithe', 'Smyth', 'Smythe', 'Smijth']

(but, of course, you will have to be careful with this feature in order to reduce false positives)

hth,
vbr

 

[BrJohan]

For some genealogical purposes I consider using Python's re module.

Rather many names can be spelled in a number of similar ways, and in order to match names even if they are spelled differently, I will build regular expressions, each of which is supposed to match a number of similar names.

I guess that there will be a few hundred such regular expressions covering most popular names.

Now, my problem: Is there a way to decide whether any two - or more - of those regular expressions will match the same string?

Or, stated a little differently:

Can it, for a pair of regular expressions be decided whether at least one string matching both of those regular expressions, can be constructed?

If it is possible to make such a decision, then how? Anyone aware of an algorithm for this?

Thank you all for valuable input and interesting thoughts.

After having reconsidered my problem, it might be better to approach it a little differently.

Either to state the regexps simply like:
"(Kristina)|(Christina)|(Cristine)|(Kristine)"
instead of "((K|(Ch))ristina)|([CK]ristine)"

Or to put the namevariants in some sequence of sets having elements like:
("Kristina", "Christina", "Cristine", "Kristine")
Matching is then just applying the 'in' operator.

I see two distinct advantages.
1. Readability and maintainability
2. Any namevariant occurring in just one regexp or set means no risk of erroneous matching.

Comments?

 

[Peter Otten]

For some genealogical purposes I consider using Python's re module.

Rather many names can be spelled in a number of similar ways, and in order to match names even if they are spelled differently, I will build regular expressions, each of which is supposed to match a number of similar names.

I guess that there will be a few hundred such regular expressions covering most popular names.

Now, my problem: Is there a way to decide whether any two - or more - of those regular expressions will match the same string?

Or, stated a little differently:

Can it, for a pair of regular expressions be decided whether at least one string matching both of those regular expressions, can be constructed?

If it is possible to make such a decision, then how? Anyone aware of an algorithm for this?

Thank you all for valuable input and interesting thoughts.

After having reconsidered my problem, it might be better to approach it a little differently.

Either to state the regexps simply like:
"(Kristina)|(Christina)|(Cristine)|(Kristine)"
instead of "((K|(Ch))ristina)|([CK]ristine)"

Or to put the namevariants in some sequence of sets having elements like:
("Kristina", "Christina", "Cristine", "Kristine")
Matching is then just applying the 'in' operator.

I see two distinct advantages.
1. Readability and maintainability
2. Any namevariant occurring in just one regexp or set means no risk of erroneous matching.

Comments?

I like the simple variant

kristinas = ("Kristina", "Christina", "Cristine", "Kristine")

But instead of matching with "in" you could build a dict that maps the name variants to a normalised name

normalized_names = {
"Kristina": "Kristina",
"Christina": "Kristina",
...
"John": "John",
"Johann": "John",
...
}
def normalized(name):
return normalized_names.get(name, name)

If you put persons in another dict or a database indexed by the normalised name

lookup = {
"Kristina": ["Kristina Smith", "Christina Miller"],
...
}

you can find all Kristinas with two look-ups:

lookup[normalized("Kristine")]

['Kristina Smith', 'Christina Miller']

PS: A problem with this approach might be that (name in nameset_A) and (name in nameset_B) implies nameset_A == nameset_B

 

[Tony the Tiger]

I guess that there will be a few hundred such regular expressions covering most popular names.

Perhaps

http://code.activestate.com/recipes/52213-soundex-algorithm/ https://en.wikipedia.org/wiki/Soundex

will work?

/Grrr