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

Question

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.

3. Search for words that start with "x"

4. Search for words that end with "x"

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

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

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

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

8. 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.

Answer 1

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"} *)