Word Pattern Finder

Problem: find all words that follow a pattern (independently from the actual symbols used to define the pattern).

Almost identical to what this site does:

Enter patterns like: ABCCDE
This will find words like "bloody", "kitten", and "valley". The above pattern will NOT find words like "fennel" or "hippie" because that would require the pattern to be ABCCBE.

Please note: I need a version of that algorithm that does find words like "fennel" or "hippie" even with an ABCCDE pattern.

To complicate things further, there is the possibility to add known characters anywhere in the searching pattern, for example: cBBX (where c is the known character) will yield cees, coof, cook, cool ...

What I've done so far: I found this answer (Pattern matching for strings independent from symbols) that solves my problem almost perfectly, but if I assign an integer to every word I need to compare, I will encounter two problems.

The first is the number of unique digits I can use. For example, if the pattern is XYZABCDEFG, the equivalent digit pattern will be 1 2 3 4 5 6 7 8 9 and then? 10? Consider that I would use the digit 0 to indicate a known character (for example, aBe --> 010 --> 10). Using hexadecimal digits will move the problem further, but will not solve it.

The second problem is the maximum length of the pattern: a Long in Java is 19-digit long, and I need no restriction in my patterns (although I don't think there exists a word with 20 different characters).

To solve those problems, I could store each digit of the pattern in an array, but then it becomes an array-to-array comparison instead of an integer comparison, thus taking a lot more time to compute.

As a side note: according to the algorithm used, what data structure will be the best suited for storing the dictionary? I was thinking about using an hash-map, converting each word into its digit-pattern equivalent (assuming no known character) and using this number as an hash (of course, there would be a lot of collisions). In that way searching will require first to match the numeric pattern, and then to scan the results to find all the words that have the known characters at the right place (if present in the original searching pattern).

Also, the dictionary is not static: words can be added and deleted.

EDIT:

This answer () works fairly well and it's fast (testing for equal lengths before matching the patterns). The only problem is that I need a version of that algorithm that find words like "fennel" or "hippie" even with an ABCCDE pattern.

I've already implemented a way to check for known characters.

EDIT 2:

Ok, by checking if each character in the pattern is greater or equal than the corresponding character in the current word (normalized as a temporary pattern) I am almost done: it correctly matches the search pattern ABCA with the word ABBA and it correctly ignores the word ABAC. The last problem remaining is that if (for example) the pattern is ABBA it will match the word ABAA, and that's not correct.

EDIT 3:

Meh, not pretty but it seems to be working (I'm using Python because it's fast to code with it). Also, the search pattern can be any sequence of symbols, using lowercase letters as fixed characters and everything else as wildcards; there is also no need to convert each word in an abstract pattern.

 def match(pattern, fixed_chars, word): d = dict() if len(pattern) != len(word): return False if check_fixed_char(word, fixed_chars) is False: return False for i in range(0, len(pattern)): cp = pattern[i] cw = word[i] if cp in d: if d[cp] != cw: return False else: d[cp] = cw if cp > cw: return False return True 

2 Answers

A long time ago I wrote a program for solving cryptograms which was based on the same concept (generating word patterns such that "kitten" and "valley" both map to "abccde."

My technique did involve generating a sort of index of words by pattern.

The core abstraction function looks like:

#!python #!/usr/bin/env python import string def abstract(word): '''find abstract word pattern dog or cat -> abc, book or feel -> abbc ''' al = list(string.ascii_lowercase) d = dict for i in word: if i not in d: d[i] = al.pop(0) return ''.join([d[i] for i in word]) 

From there building our index is pretty easy. Assume we have a file like /usr/share/dict/words (commonly found on Unix-like systems including MacOS X and Linux):

#!/usr/bin/python words_by_pattern = dict() words = set() with open('/usr/share/dict/words') as f: for each in f: words.add(each.strip().lower()) for each in sorted(words): pattern = abstract(each) if pattern not in words_by_pattern: words_by_pattern[pattern] = list() words_by_pattern[pattern].append(each) 

... that takes less than two seconds on my laptop for about 234,000 "words" (Although you might want to use a more refined or constrained word list for your application).

Another interesting trick at this point is to find the patterns which are most unique (returns the fewest possible words). We can create a histogram of patterns thus:

histogram = [(len(words_by_pattern[x]),x) for x in words_by_pattern.keys()] histogram.sort() 

I find that the this gives me:

8077 abcdef 7882 abcdefg 6373 abcde 6074 abcdefgh 3835 abcd 3765 abcdefghi 1794 abcdefghij 1175 abc 1159 abccde 925 abccdef 

Note that abc, abcd, and abcde are all in the top ten. In other words the most common letter patterns for words include all of those with no repeats among 3 to 10 characters.

You can also look at the histogram of the histogram. In other words how many patterns only show one word: for example aabca only matches "eerie" and aabcb only matches "llama". There are over 48,000 patterns with only a single matching word and almost six thousand with just two words and so on.

Note: I don't use digits; I use letters to create the pattern mappings.

I don't know if this helps with your project at all; but this are very simple snippets of code. (They're intentionally verbose).

This can easily be achieved through using Regular Expressions. For example, the below pattern matches any word that has ABCCDE pattern:

(?:([A-z])(?!\1)([A-z])(?!\1|\2)([A-z])(?=\3)([A-z])(?!\1|\2|\3|\5)([A-z])(?!\1|\2|\3|\5|\6)([A-z])) 

And this one matches ABCCBE:

(?:([A-z])(?!\1)([A-z])(?!\1|\2)([A-z])(?=\3)([A-z])(?=\2)([A-z])(?!\1|\2|\3|\5|\6)([A-z])) 

To cover both above pattern, you can use:

(?:([A-z])(?!\1)([A-z])(?!\1|\2)([A-z])(?=\3)([A-z])(?(?=\2)|(?!\1\2\3\5))([A-z])(?!\1|\2|\3|\5|\6)([A-z])) 

Going this path, your challenge would be generating the above Regex pattern out of the alphabetic notation you used. And please note that you may want to use the i Regex flag when using these if case-insensitivity is a requirement.

For more Regex info, take a look at:
Look-around
Back-referencing