# N-gram generation

I have the following code, but it's too slow. How can I make it faster?

<?php
class Ngram {

const SAMPLE_DIRECTORY = "samples/";
const GENERATED_DIRECTORY = "languages/";
const SOURCE_EXTENSION = ".txt";
const GENERATED_EXTENSION = ".lng";
const N_GRAM_MIN_LENGTH = "1";
const N_GRAM_MAX_LENGTH = "6";

public function __construct() {
mb_internal_encoding( 'UTF-8' );
$this->generateNGram(); } private function getFilePath() {$files = array();
$excludes = array('.', '..');$path = rtrim(self::SAMPLE_DIRECTORY, DIRECTORY_SEPARATOR . '/');
$files = scandir($path);
$files = array_diff($files, $excludes); foreach ($files as $file) { if (is_dir($path . DIRECTORY_SEPARATOR . $file)) fetchdir($path . DIRECTORY_SEPARATOR . $file,$callback);
else if (!preg_match('/^.*\\' . self::SOURCE_EXTENSION . '$/',$file))
continue;
else
$filesPath[] =$path . DIRECTORY_SEPARATOR . $file; } unset($file);
return $filesPath; } protected function removeUniCharCategories($string){
//Replace punctuation(' " # % & ! . : , ? ¿) become space " "
//Example : 'You&me', become 'You Me'.
$string = preg_replace( "/\p{Po}/u", " ",$string );
//--------------------------------------------------
$string = preg_replace( "/[^\p{Ll}|\p{Lm}|\p{Lo}|\p{Lt}|\p{Lu}|\p{Zs}]/u", "",$string );
$string = trim($string);
$string = mb_strtolower($string,'UTF-8');
return $string; } private function generateNGram() {$files = $this->getFilePath(); foreach($files as $file) {$file_content = file_get_contents($file, FILE_TEXT);$file_content = $this->removeUniCharCategories($file_content);
$words = explode(" ",$file_content);
$tokens = array(); foreach ($words as $word) {$word = "_" . $word . "_";$length = mb_strlen($word, 'UTF-8'); for ($i = self::N_GRAM_MIN_LENGTH, $min = min(self::N_GRAM_MAX_LENGTH,$length); $i <=$min; $i++) { for ($j = 0, $li =$length - $i;$j <= $li;$j++) {
$token = mb_substr($word, $j,$i, 'UTF-8');
if (trim($token, "_")) {$tokens[] = $token; } } } } unset($word);
$tokens = array_count_values($tokens);
arsort($tokens);$ngrams = array_slice(array_keys($tokens), 0); file_put_contents(self::GENERATED_DIRECTORY . str_replace(self::SOURCE_EXTENSION, self::GENERATED_EXTENSION, basename($file)), implode(PHP_EOL, $ngrams)); } unset($file);
}
}
$ii = new Ngram(); ?>  ## 2 Answers This code seems to be very good as far as performance is concerned. I cannot see any way to improve it. I used xdebug and cachegrind to see that my test samples were bound by the performance of the loop that creates the tokens. I investigated switching the$i and $j loops around, but the performance was no better. I cannot see any way to improve the code, so I would look at a faster CPU or a compiled language like C. There are also large improvements in performance with PHP 5.4, so moving to that might be a very good option. ## Response to Other Answer We now have two answers both claiming different bottlenecks. This makes things interesting! I'll list the evidence that makes me believe it is a CPU bottleneck. The first evidence I'll investigate will be the profiling information. The second will be a simple proof of removing the I/O and observing the runtimes. Skip to the second in the "Removed I/O" section if you just want the quick answer. ## Profiling The tools I am using are xdebug and kcachegrind. First I created four some sample files. My first 3 files were lorem ipsum type texts in Greek, Chinese and Latin. My fourth was the concatenation of these three files and is shown below: 遺健問使物済表績象全問前禎。画更予服的負要前行年語断。肉購会際以面長力攻以野所。治条育録療常強門守更校尊無場審言団。早患社支科視徐取告性表変全意主場。度坂信神暮明死載高深典導昇話。無稿乳横面祝揚倉厘積卒食当正使。食考割闘出護空樫京速地間作夜半文性新局。前馬報惑般供筋子真車東生然歌論略形。政図警情調並浜校素先間後善経完。 Lorem ipsum dolor sit amet, eu ius nisl impedit. Tritani denique ut nam, brute aliquid iudicabit eos ei. Ad vix hinc numquam, unum utamur vix cu. Natum ubique vocibus ei duo. Quo te eius propriae voluptatibus, id nostro forensibus signiferumque est, graecis senserit gloriatur per et. Eu munere facete scripserit vel, cu vim laudem noster. His cu dictas prodesset, aliquando constituto reprimique sed ex. Mazim decore imperdiet ut vel. Scripta delicatissimi an pro, quo ex porro nominati. Δε τις έργων κανείς γραμμή, κι χρόνου φακέλους γειτονιάς ήδη. Σε πακέτων επενδυτής λες, που κρατήσουν επεξεργασία δε, μια ακούσει ξεχειλίζει παρατηρούμενη τα. Νέων πετάνε συνηθίζουν δε για', στη να σωστά ευκολότερο βαθμολόγησε. Απλό τέτοιο διοίκηση στα μη, δε νέο τότε περιβάλλον, οι δώσε απαρατήρητο των. Βαθμολόγησε επιδιόρθωση επιχειρηματίες αν ματ, σου δεδομένη αγοράζοντας δωροδοκηθούν με, τα ένα αναφορά βουτήξουν. Αν καρέκλα υποψήφιο εξαρτάται όσο, και δε τεράστιο προκύπτουν σημαντικός, αν ναι καθώς διορθώσει. Υόρκη ιδιαίτερα τη άρα, τα λοιπόν παράγοντες μας. Πόρτες γραμμές σκεφτείς λες με. Σου βγήκε αρχεία δε. Και εφαμοργής κακόκεφος δε.  I then ran the code, with a small modification to help benchmarking: $startTime = microtime(true);

for ($i = 1;$i <= 10; $i++) {$ii = new Ngram();
}

$finishTime = microtime(true); echo 'Took: ' . ($finishTime - $startTime) . 'seconds';  It took about 0.61 seconds without xdebug enabled and 29.1 seconds with it. Note how much slower it is with xdebug (it takes a lot of time to keep track of the execution for profiling)! I then observed the xdebug information using kcachegrind: You can see that the time listed against file_put_contents (which is highlighted in the image is very small. Of the 29.1 seconds it only spends .01 seconds writing the files (4 of them). This was on my SSD with an ext4 filesystem. You can see that there are 40 calls to file_put_contents 4 files, 10 times each. Actually, more time is spent by getFilePath which has more costly file stat operations. The more interesting part is how the 29 seconds gets spent in generateNGram. I have a picture of what I believe to be the "hot" part of the code: We get into 4 levels of looping here where there are 121280 calls to the inner loop functions. There are no times listed for the for loop structures or the addition to the tokens array ($tokens[] = \$token;). I don't exactly know where the 29 seconds got used, but I am assuming that it was within these loops.

## Removed I/O

The simple way of determining whether this is I/O bound is to remove the I/O. I commented out the file_put_contents line and ran the benchmark again. I found that there was no difference in time with 0.63 seconds without xdebug and 29.2 seconds with it (compared to 0.61 and 29.1). It was actually slower (due to timing fluctuations), but this just shows the negligible influence of the I/O.

## Summary

I still believe this is a CPU bottleneck and maintain my recommendation for a faster CPU, PHP 5.4 or a compiled language. The other answer raises good points in the "Optimization, what for?" section.

• ngrams are generated with big corpora. It could be CPU-bound indeed, but this provides little evidence since you can't be I/O-bound with just a few words to read. (oh, and I upvoted.) If it's not IO-bound, then there's a lot of room for optimization. It's easy to imagine a "char-based" parser whith very little CPU overhead (and will avoid costly explode, strlen and so on). – Quentin Pradet Apr 30 '12 at 11:28
• +1 to your answer too, I guess it would be interesting to have files of the order 1TB to make this a more realistic test. I'll leave it as unresolved, but my leaning is towards CPU-bound. – Paul Apr 30 '12 at 11:48
• After some testing with bigger corpora (gutenberg books), it's defintely CPU-bound. What do your languages/*.lng files look like? It's complete gibberish here. If it was normal word n-grams then I could have written a better implementation based on a queue of length N_GRAM_MAX_LENGTH. But I have no idea what he's doing. – Quentin Pradet Apr 30 '12 at 12:32
• It seems that it is unique segments, I'm seeing output in the file including whether they are from the _start or end_ of a word (note the underscores). I'm not really sure what it is for or if that was the intention. – Paul Apr 30 '12 at 13:14

After some testing, it's CPU-bound. I also hit PHP maximum allowed memory size when working with larger files: it eats more than 3G of memory when loading a 4M file. Try reducing the memory usage. :)

## I/O bottleneck

It's quite obvious that you're going to create a lot of data. The Google Ngram corpus, for example, uses 1To of disk space. You probably have less data, but you're still going to generate a lot of bytes, which suggests that your program is not CPU-bound, but IO-bound. This also means that using a faster CPU or another language wouldn't help at all.

## A lower bound

Let's try to work out a lower bound to see what improvements can be made. Since you can't go any faster than a program simply writing the ngrams without any calculation, you should try copying your ngrams data to another folder to see how long it would take. Using "cp" would be dangerous, since there may be crazy optimizations like copy-on-write on your specific filesystem.

time cat ngrams/* > all_my_ngrams
time cat corpus/* > all_my_corpus


You can then compare this to the time it takes for your program to complete, and see where you're losing your time. Another option is to use microtime to benchmark the time you take to actually do computations, and the time to file_get_contents and file_put_contents.

## Optimization, what for?

Since it's probably a one-off script, why do you want to make it fast? Once you have your ngrams, you can reuse them and forget about this script. Is there a good reason to improve this script? If the problem is more specific than "takes too long", than we can help: too much RAM? takes months? Specific strategies can help for specific problems.

• That is a very good point. This will probably be memory bound! Keeping a count of the tokens within the inner for loop rather than just adding them would help with this. – Paul May 1 '12 at 4:49