# How to implement search patterns and take into account language statistics?

Patterns in Mathematica

I struggle some with patterns while trying to extract words out of large texts. Let us say that I have a long text (Strindberg) that we can call dictionary.

I have implemented the flowing extracting filters.

1. Search for words containing both "x" and "y" in that order

Select[dictionary, With[{pat = #}, StringLength[pat] == i && StringMatchQ[#, ___ ~~ "x" ~~ __ ~~ "y" ~~ ___] &]]

2. Search for words that start with "x"

Select[dictionary, With[{pat = #}, StringLength[pat] == i && StringMatchQ[#, "x" ~~ ___] &]]


…and a few others. I can post them if there is any interest.

1. Search for words that start with "x"

2. Search for words that end with "x"

3. Search for words that contain "x" or "y" in any order

QUESTION. I also would like to have the following filters.

1. Search for words that contain both "x" and "y", but in any order

2. Search for words that contain "x" but not "y"

3. Then I would like to refine the outputs above but taking into consideration the statistics of the language at hand. Some words from the results above might include unusual letters (z,w) not common in Swedish. Those words should be in the results but in a tail, i e first quite common words (with common letters with high occurrence frequency) and then more exotic words (with uncommon letters).

The issue in 8 is especially important but I cannot find how to implement a solution. How does one include statistics of the language in search algorithms? I have a list of the occurrences of the Swedish letters.

Any pointers in the correct direction would be much appreciated. Thank you very much in advance.

• Answers to 5, 6, and 7: Select[{"xy", "x", "y"}, ! StringFreeQ[#, {"x", "y"}] &] Select[{"xy", "x", "y"}, Not[StringFreeQ[#, "x"] || StringFreeQ[#, "y"]] &], and Select[{"xy", "x", "y"}, StringFreeQ[#, "y"] && Not@StringFreeQ[#, "x"] &] – march Jun 21 '16 at 21:46

For (6) you need to specify two patterns, one for each ordering:

words = {"abcd", "aydx", "axdy", "adx"};
Select[
words,
StringContainsQ[("x" ~~ ___ ~~ "y") | ("y" ~~ ___ ~~ "x")]
]

(* Out: {"aydx", "axdy"} *)


StringContainsQ, StringStartsQ and StringEndQ can be used for some of your patterns and may either give a performance boost or at the very least be easier to read. They were introduced in Mathematica 10.1.

For (7) you can use Except:

Pick[
words,
StringMatchQ[words, Except["y"] ... ~~ "x" ~~ Except["y"] ...]
]

(* Output: {"adx"} *)


Note that I'm using the listability of StringMatchQ here which probably gives a performance boost. This can also be used with StringContainsQ etc.

For (8) note that Select (and Pick) preserves the order of matches, I would therefore sort the dictionary. You can compute what the scores of the words are in Scrabble for example and use that to sort the dictionary. Another option could be to assign the least common letter a score of 1 and then use the word frequencies to assign scores to the rest of the letters relative to this score.

It could look like this:

score["a"] = 1;
score["b"] = 2;
score["c"] = 3;
score["d"] = 4;
score["x"] = 5;
score["y"] = 6;
scoreString[str_] := Total[score /@ Characters[str]]
SortBy[words, scoreString]

(* Out: {"abcd", "adx", "axdy", "aydx"} *)

• Thank you very much for your suggestions. I am travelling so I cannot apply them to my problems. Will be back asap. – JSP Jun 24 '16 at 7:17
• I have now (at last!) tried these possibilities and they work nicely on my word lists. Thank you very much! I did not know about StringEndsQ etc. and those are a great step forward. I am trying to understand and apply the suggestion for the statistics (8) but fail to understand why the score of a is 1 while x gets a 5, and y a 6 (in contrast you write that "the leat common letter should have a score of !"). It seems contradictory to me!? – JSP Jul 18 '16 at 15:16
• @JSP I'm only assigning some numbers to show what the code would look like... a = 1, b = 2, c = 3, d = 4 is not my suggestion for how letters should be ranked in the Swedish alphabet! Look up appropriate rankings in Alfapet or by counting the occurrence of letters in a set of texts. – C. E. Jul 18 '16 at 15:32
• Ah OK, thank you. I understood you were not speaking about the Swedish alphabet but thought that I had misunderstood. I have the Statistics of the occurrences and have sorted the list according to your suggestion. Suppose that list has 20 thousand words. How would I pick 50 words from the beginning of the list (=more common words), given some small set of letters(m,p,a)? Should I use StringContainsQ[#,{m,p,a}] – JSP Jul 18 '16 at 15:43
• @JSP Yes, unless you run into efficiency issues the way to do this is to first filter out all words that don't contain those letters and then pick the first fifty elements of the filtered list. – C. E. Jul 19 '16 at 6:10