3
$\begingroup$

There are many resources online showing how to get the most frequent letters in the english language. What I'm trying to do is get the most common word prefixes in the english language - i.e, take a lot of text, and find the most common strings that begin words of length 2 or more in that text.

For the purposes of this question, I have been using the text of Hamlet. I've tried many things but I'm not sure how to approach this algorithmically, let alone implementing it.

How can I find the most common prefixes in the english language based on some text?

$\endgroup$
1
$\begingroup$
mytext = "Now is the time for all good men to come to the aid of their party";

Flatten[
        Table[{i <> j, 
             Length[StringCases[mytext, 
             Shortest[WordBoundary ~~ i <> j ~~ __ ~~ WordBoundary]]]}, 
        {i, CharacterRange["a", "z"]}, 
        {j, CharacterRange["a", "z"]}], 
  1] // TableForm

Just replace mytext with your Hamlet text.

Here are the results for the First Act, up to Horatio's speech starting "That can I..."

  {{"th", 65}, {"to", 23}, {"of", 22}, {"an", 21}, {"no", 14}, {"st", 
  12}, {"ha", 12}, {"yo", 11}, {"ni", 10}, {"it", 10}, {"he", 
  10}, {"so", 9}, {"ma", 9}, {"be", 9}, {"sp", 8}, {"wa", 7}, {"ki", 
  7}, {"co", 7}, {"wh", 6}, {"on", 6}, {"li", 6}, {"hi", 6}, {"go", 
  6}, {"wi", 5}, {"we", 5}, {"us", 5}, {"tw", 5}, {"se", 5}, {"ou", 
  5}, {"my", 5}, {"mo", 5}, {"ho", 5}, {"ca", 5}, {"ar", 5}, {"ag", 
  5}, {"si", 4}, {"sa", 4}, {"pa", 4}, {"mi", 4}, {"me", 4}, {"fr", 
  4}, {"fo", 4}, {"fa", 4}, {"do", 4}, {"ap", 4}, {"wo", 3}, {"ti", 
  3}, {"su", 3}, {"lo", 3}, {"le", 3}, {"la", 3}, {"is", 3}, {"in", 
  3}, {"gr", 3}, {"da", 3}, {"ch", 3}, {"bu", 3}, {"at", 3}, {"tr", 
  2}, {"ta", 2}, {"sc", 2}, {"re", 2}, {"qu", 2}, {"pr", 2}, {"po", 
  2}, {"pl", 2}, {"ne", 2}, {"kn", 2}, {"im", 2}, {"ey", 2}, {"di", 
  2}, {"de", 2}, {"by", 2}, {"br", 2}, {"bi", 2}, {"aw", 2}, {"am", 
  2}, {"al", 2}, {"ve", 1}, {"up", 1}, {"un", 1}, {"tu", 1}, {"te", 
  1}, {"sw", 1}, {"sm", 1}, {"sl", 1}, {"sh", 1}, {"ri", 1}, {"pi", 
  1}, {"ow", 1}, {"ot", 1}, {"op", 1}, {"ob", 1}, {"mu", 1}, {"ju", 
  1}, {"jo", 1}, {"il", 1}, {"if", 1}, {"ic", 1}, {"gu", 1}, {"ge", 
  1}, {"fi", 1}, {"fe", 1}, {"er", 1}, {"en", 1}, {"ea", 1}, {"dr", 
  1}, {"bo", 1}, {"av", 1}, {"as", 1}}
$\endgroup$
  • $\begingroup$ Thank you for your answer! I already had something similar to this, but I should clarify - I'm trying to find the most common prefixes in a certain text, i.e in actual use in the english language, not just from a dictionary. $\endgroup$ – TreFox Oct 9 '17 at 18:30
  • 1
    $\begingroup$ Why not identify the common prefixes using David's method (maybe extend to 3 letters as well) and then, once you have the list, search your text for them $\endgroup$ – bill s Oct 9 '17 at 18:39
  • $\begingroup$ @bill S That's a great idea! Thank you! $\endgroup$ – TreFox Oct 9 '17 at 18:42
1
$\begingroup$

This answer uses the package TriesWithFrequencies.m described in the blog post "Tries with frequencies for data mining".

This loads the package:

Import["https://raw.githubusercontent.com/antononcube/MathematicaForPrediction/master/TriesWithFrequencies.m"]

This gets the words from "Hamlet" and converts to lower case:

tWords = TextWords[ExampleData[{"Text", "Hamlet"}]];
tWords = ToLowerCase[tWords];
Length[tWords]

(* 31874 *)

This creates the trie and converts the frequencies to probabilities:

AbsoluteTiming[
 pTr = TrieNodeProbabilities[TrieCreate[tWords]];
]

(* {6.01861, Null} *)

Trie nodes counts:

TrieNodeCounts[pTr]

(* <|"total" -> 14276, "internal" -> 10502, "leaves" -> 3774|> *)

The following code prunes the trie in correspondence to a given prefix length and then finds the corresponding probabilities for each prefix. The result is given as an Association.

maxPrefixLength = 3;
paths = Rest /@ TrieRootToLeafPaths[TriePrune[pTr, maxPrefixLength]];
aPaths = Map[<|"path" -> Apply[StringJoin, #[[All, 1]]], 
     "probability" -> Apply[Times, #[[All, 2]]]|> &, paths];

From this Pareto principle adherence plot we can see that 20% of the 3-letter prefixes are correspond to 80% of the words in "Hamlet":

ParetoLawPlot[Through[aPaths["probability"]]]

enter image description here

This finds quantile values within the 10% of the most popular prefixes:

Quantile[Through[aPaths["probability"]], Range[0.9, 1, 0.025]]

(* {0.00125494, 0.00169417, 0.00257263, 0.00370208, 0.0528958} *)

This selects the most popular prefixes for a given probability:

Select[aPaths, #["probability"] >= %[[-2]] &]

(* {<|"path" -> "que", "probability" -> 0.00429817|>, <|"path" -> "kin", 
  "probability" -> 0.00715317|>, <|"path" -> "wil", 
  "probability" -> 0.00605509|>, <|"path" -> "wit", 
  "probability" -> 0.0110435|>, <|"path" -> "whe", 
  "probability" -> 0.00464328|>, <|"path" -> "wha", 
  "probability" -> 0.00696492|>, <|"path" -> "you", 
  "probability" -> 0.0267616|>, <|"path" -> "let", 
  "probability" -> 0.00370208|>, <|"path" -> "lor", 
  "probability" -> 0.00737278|>, <|"path" -> "his", 
  "probability" -> 0.00944343|>, <|"path" -> "him", 
  "probability" -> 0.00680806|>, <|"path" -> "her", 
  "probability" -> 0.00542762|>, <|"path" -> "hea", 
  "probability" -> 0.00624333|>, <|"path" -> "hor", 
  "probability" -> 0.00545899|>, <|"path" -> "hav", 
  "probability" -> 0.00586685|>, <|"path" -> "ham", 
  "probability" -> 0.0148397|>, <|"path" -> "but", 
  "probability" -> 0.00843948|>, <|"path" -> "our", 
  "probability" -> 0.00429817|>, <|"path" -> "all", 
  "probability" -> 0.00401581|>, <|"path" -> "are", 
  "probability" -> 0.00407856|>, <|"path" -> "and", 
  "probability" -> 0.0307147|>, <|"path" -> "not", 
  "probability" -> 0.0110749|>, <|"path" -> "pol", 
  "probability" -> 0.00432955|>, <|"path" -> "com", 
  "probability" -> 0.00655707|>, <|"path" -> "sho", 
  "probability" -> 0.00389032|>, <|"path" -> "sha", 
  "probability" -> 0.00467466|>, <|"path" -> "for", 
  "probability" -> 0.0115141|>, <|"path" -> "tho", 
  "probability" -> 0.00611784|>, <|"path" -> "tha", 
  "probability" -> 0.0149024|>, <|"path" -> "thi", 
  "probability" -> 0.0129573|>, <|"path" -> "the", 
  "probability" -> 0.0528958|>} *)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.