FASTSUBS Copyright (c) 2012-2014 Deniz Yuret Usage: fastsubs [-n <n> | -p <p>] model.lm[.gz] < input.txt Fastsubs is a program that finds the most likely substitutes for words in input.txt using the language model in model.lm (ARPA format). The number of substitutes is controlled by two parameters: -n specifies the number of substitutes for each word, -p specifies a threshold on the sum of the substitute probabilities. The program stops generating substitutes for a word when either limit is satisfied. The output has an input word and its substitutes with the logarithm (base 10) of their unnormalized probabilities in the following format: word <tab> sub1 <space> lprob1 <tab> sub2 <space> lprob2 <tab> ... Please see the file LICENSE for terms of use. A paper with the description of the algorithm and other related resources can be found at http://goo.gl/jzKH0. The code is mostly C99 compliant and has been compiled and tested on a linux system with gcc. The few GNU extensions used are optional and can be turned off by editing the beginning of dlib.h. Update of Jan 9, 2014: The latest version gets rid of all glib dependencies (glib is broken, it blows up your code without warning if your arrays or hashes get too big). It also fixes a bug: The previous versions of the code and the paper assumed that the log back-off weights were upper bounded by 0 which they are not. In my standard test of generating the top 100 substitutes for all the 1,222,974 positions in the PTB, this caused a total of 66 low probability substitutes to be missed and 31 to be listed out of order. Finally a multithreaded version, fastsubs-omp is implemented. The number of threads can be controlled using the environment variable OMP_NUM_THREADS. fastsubs-omp can be used with a few additional run-time options: Usage: fastsubs-omp [-n <n> | -p <p> | -m <max-threads> | -t | -z ] model.lm[.gz] < input.txt -m specifies the maximum number of threads that can be used -z specifies that the output probability values would be normalized probabilities that sum up to 1 (instead of the default unnormalized log probabilities) -t specifies a one-target-per-text-line input format (instead of the default free text format). In this format every input line is: target_name <tab> target_id <tab> target_index <tab> text_line Then for every input line fastsubs-omp outputs two lines: 1) the input line 2) substitutes for the text_line[target_index] (i.e. the word in the target_index position in text_line) in the format: sub1 <space> lprob1 <tab> sub2 <space> lprob2 <tab> ... Other test and utility executables that can be built using the Makefile: * fastsubs-omp: Multithreaded version. * wordsub: Takes the output of fastsubs and samples random substitutes for each word. * normalize-subs.pl: Takes fastsubs output and converts the unnormalized log10(p) entries to normalized p entries that add up to 1.0 (which may not be accurate if fastsubs did not output the whole vocabulary.) * fastsubs-test: Takes a model file and interactively runs fastsubs on sentences typed by the user. * lmheap-test: Takes a model file and tests the heaps in the lm data structure by interactively reading n-grams from the user and printing out the contents of the heap for each position. * sentence-test: Takes a model file and tests the sentence and lm data structures by reading sentences from the user and printing out logp for each word. * lm-test: Takes a model file and tests the lm data structure by reading n-grams from the user and printing out their logp and back-off weights.