Merge remote-tracking branch 'upstream/master'

103 files changed, 7398 insertions, 0 deletions

diff --git a/extractor/Makefile.am b/extractor/Makefile.am
new file mode 100644
index 00000000..e94a9b91
--- /dev/null
+++ b/extractor/Makefile.am
@@ -0,0 +1,152 @@
+if HAVE_CXX11
+
+bin_PROGRAMS = compile run_extractor
+
+EXTRA_PROGRAMS = alignment_test \
+    data_array_test \
+    fast_intersector_test \
+    feature_count_source_target_test \
+    feature_is_source_singleton_test \
+    feature_is_source_target_singleton_test \
+    feature_max_lex_source_given_target_test \
+    feature_max_lex_target_given_source_test \
+    feature_sample_source_count_test \
+    feature_target_given_source_coherent_test \
+    grammar_extractor_test \
+    matchings_finder_test \
+    phrase_test \
+    precomputation_test \
+    rule_extractor_helper_test \
+    rule_extractor_test \
+    rule_factory_test \
+    sampler_test \
+    scorer_test \
+    suffix_array_test \
+    target_phrase_extractor_test \
+    translation_table_test
+
+if HAVE_GTEST
+  RUNNABLE_TESTS = alignment_test \
+    data_array_test \
+    fast_intersector_test \
+    feature_count_source_target_test \
+    feature_is_source_singleton_test \
+    feature_is_source_target_singleton_test \
+    feature_max_lex_source_given_target_test \
+    feature_max_lex_target_given_source_test \
+    feature_sample_source_count_test \
+    feature_target_given_source_coherent_test \
+    grammar_extractor_test \
+    matchings_finder_test \
+    phrase_test \
+    precomputation_test \
+    rule_extractor_helper_test \
+    rule_extractor_test \
+    rule_factory_test \
+    sampler_test \
+    scorer_test \
+    suffix_array_test \
+    target_phrase_extractor_test \
+    translation_table_test
+endif
+
+noinst_PROGRAMS = $(RUNNABLE_TESTS)
+
+TESTS = $(RUNNABLE_TESTS)
+
+alignment_test_SOURCES = alignment_test.cc
+alignment_test_LDADD = $(GTEST_LDFLAGS) $(GTEST_LIBS) libextractor.a
+data_array_test_SOURCES = data_array_test.cc
+data_array_test_LDADD = $(GTEST_LDFLAGS) $(GTEST_LIBS) libextractor.a
+fast_intersector_test_SOURCES = fast_intersector_test.cc
+fast_intersector_test_LDADD = $(GTEST_LDFLAGS) $(GTEST_LIBS) $(GMOCK_LDFLAGS) $(GMOCK_LIBS) libextractor.a
+feature_count_source_target_test_SOURCES = features/count_source_target_test.cc
+feature_count_source_target_test_LDADD = $(GTEST_LDFLAGS) $(GTEST_LIBS) libextractor.a
+feature_is_source_singleton_test_SOURCES = features/is_source_singleton_test.cc
+feature_is_source_singleton_test_LDADD = $(GTEST_LDFLAGS) $(GTEST_LIBS) libextractor.a
+feature_is_source_target_singleton_test_SOURCES = features/is_source_target_singleton_test.cc
+feature_is_source_target_singleton_test_LDADD = $(GTEST_LDFLAGS) $(GTEST_LIBS) libextractor.a
+feature_max_lex_source_given_target_test_SOURCES = features/max_lex_source_given_target_test.cc
+feature_max_lex_source_given_target_test_LDADD = $(GTEST_LDFLAGS) $(GTEST_LIBS) $(GMOCK_LDFLAGS) $(GMOCK_LIBS) libextractor.a
+feature_max_lex_target_given_source_test_SOURCES = features/max_lex_target_given_source_test.cc
+feature_max_lex_target_given_source_test_LDADD = $(GTEST_LDFLAGS) $(GTEST_LIBS) $(GMOCK_LDFLAGS) $(GMOCK_LIBS) libextractor.a
+feature_sample_source_count_test_SOURCES = features/sample_source_count_test.cc
+feature_sample_source_count_test_LDADD = $(GTEST_LDFLAGS) $(GTEST_LIBS) libextractor.a
+feature_target_given_source_coherent_test_SOURCES = features/target_given_source_coherent_test.cc
+feature_target_given_source_coherent_test_LDADD = $(GTEST_LDFLAGS) $(GTEST_LIBS) libextractor.a
+grammar_extractor_test_SOURCES = grammar_extractor_test.cc
+grammar_extractor_test_LDADD = $(GTEST_LDFLAGS) $(GTEST_LIBS) $(GMOCK_LDFLAGS) $(GMOCK_LIBS) libextractor.a
+matchings_finder_test_SOURCES = matchings_finder_test.cc
+matchings_finder_test_LDADD = $(GTEST_LDFLAGS) $(GTEST_LIBS) $(GMOCK_LDFLAGS) $(GMOCK_LIBS) libextractor.a
+phrase_test_SOURCES = phrase_test.cc
+phrase_test_LDADD = $(GTEST_LDFLAGS) $(GTEST_LIBS) $(GMOCK_LDFLAGS) $(GMOCK_LIBS) libextractor.a
+precomputation_test_SOURCES = precomputation_test.cc
+precomputation_test_LDADD = $(GTEST_LDFLAGS) $(GTEST_LIBS) $(GMOCK_LDFLAGS) $(GMOCK_LIBS) libextractor.a
+rule_extractor_helper_test_SOURCES = rule_extractor_helper_test.cc
+rule_extractor_helper_test_LDADD = $(GTEST_LDFLAGS) $(GTEST_LIBS) $(GMOCK_LDFLAGS) $(GMOCK_LIBS) libextractor.a
+rule_extractor_test_SOURCES = rule_extractor_test.cc
+rule_extractor_test_LDADD = $(GTEST_LDFLAGS) $(GTEST_LIBS) $(GMOCK_LDFLAGS) $(GMOCK_LIBS) libextractor.a
+rule_factory_test_SOURCES = rule_factory_test.cc
+rule_factory_test_LDADD = $(GTEST_LDFLAGS) $(GTEST_LIBS) $(GMOCK_LDFLAGS) $(GMOCK_LIBS) libextractor.a
+sampler_test_SOURCES = sampler_test.cc
+sampler_test_LDADD = $(GTEST_LDFLAGS) $(GTEST_LIBS) $(GMOCK_LDFLAGS) $(GMOCK_LIBS) libextractor.a
+scorer_test_SOURCES = scorer_test.cc
+scorer_test_LDADD = $(GTEST_LDFLAGS) $(GTEST_LIBS) $(GMOCK_LDFLAGS) $(GMOCK_LIBS) libextractor.a
+suffix_array_test_SOURCES = suffix_array_test.cc
+suffix_array_test_LDADD = $(GTEST_LDFLAGS) $(GTEST_LIBS) $(GMOCK_LDFLAGS) $(GMOCK_LIBS) libextractor.a
+target_phrase_extractor_test_SOURCES = target_phrase_extractor_test.cc
+target_phrase_extractor_test_LDADD = $(GTEST_LDFLAGS) $(GTEST_LIBS) $(GMOCK_LDFLAGS) $(GMOCK_LIBS) libextractor.a
+translation_table_test_SOURCES = translation_table_test.cc
+translation_table_test_LDADD = $(GTEST_LDFLAGS) $(GTEST_LIBS) $(GMOCK_LDFLAGS) $(GMOCK_LIBS) libextractor.a
+
+noinst_LIBRARIES = libextractor.a libcompile.a
+
+compile_SOURCES = compile.cc
+compile_LDADD = libcompile.a
+run_extractor_SOURCES = run_extractor.cc
+run_extractor_LDADD = libextractor.a
+
+libcompile_a_SOURCES = \
+  alignment.cc \
+  data_array.cc \
+  phrase_location.cc \
+  precomputation.cc \
+  suffix_array.cc \
+  time_util.cc \
+  translation_table.cc
+
+libextractor_a_SOURCES = \
+  alignment.cc \
+  data_array.cc \
+  fast_intersector.cc \
+  features/count_source_target.cc \
+  features/feature.cc \
+  features/is_source_singleton.cc \
+  features/is_source_target_singleton.cc \
+  features/max_lex_source_given_target.cc \
+  features/max_lex_target_given_source.cc \
+  features/sample_source_count.cc \
+  features/target_given_source_coherent.cc \
+  grammar.cc \
+  grammar_extractor.cc \
+  matchings_finder.cc \
+  matchings_trie.cc \
+  phrase.cc \
+  phrase_builder.cc \
+  phrase_location.cc \
+  precomputation.cc \
+  rule.cc \
+  rule_extractor.cc \
+  rule_extractor_helper.cc \
+  rule_factory.cc \
+  sampler.cc \
+  scorer.cc \
+  suffix_array.cc \
+  target_phrase_extractor.cc \
+  time_util.cc \
+  translation_table.cc \
+  vocabulary.cc
+
+AM_CPPFLAGS = -W -Wall -Wno-sign-compare $(CXX11_SWITCH) -fopenmp $(GTEST_CPPFLAGS) $(GMOCK_CPPFLAGS)
+AM_LDFLAGS = -fopenmp
+endif
diff --git a/extractor/README.md b/extractor/README.md
new file mode 100644
index 00000000..575f5ca5
--- /dev/null
+++ b/extractor/README.md
@@ -0,0 +1,14 @@
+C++ implementation of the online grammar extractor originally developed by [Adam Lopez](http://www.cs.jhu.edu/~alopez/).
+
+To run the extractor you need to:
+
+    cdec/extractor/run_extractor -a <alignment> -b <parallel_corpus> -g <grammar_output_path> < <input_sentences> > <sgm_file>
+
+To run unit tests you need first to configure `cdec` with the [Google Test](https://code.google.com/p/googletest/) and [Google Mock](https://code.google.com/p/googlemock/) libraries:
+
+    ./configure --with-gtest=</absolute/path/to/gtest> --with-gmock=</absolute/path/to/gmock>
+
+Then, you simply need to:
+
+    cd cdec/extractor
+    make check
diff --git a/extractor/alignment.cc b/extractor/alignment.cc
new file mode 100644
index 00000000..1aea34b3
--- /dev/null
+++ b/extractor/alignment.cc
@@ -0,0 +1,53 @@
+#include "alignment.h"
+
+#include <fstream>
+#include <sstream>
+#include <string>
+#include <fcntl.h>
+#include <unistd.h>
+#include <vector>
+
+#include <boost/algorithm/string.hpp>
+#include <boost/filesystem.hpp>
+
+namespace fs = boost::filesystem;
+using namespace std;
+
+namespace extractor {
+
+Alignment::Alignment(const string& filename) {
+  ifstream infile(filename.c_str());
+  string line;
+  while (getline(infile, line)) {
+    vector<string> items;
+    boost::split(items, line, boost::is_any_of(" -"));
+    vector<pair<int, int> > alignment;
+    alignment.reserve(items.size() / 2);
+    for (size_t i = 0; i < items.size(); i += 2) {
+      alignment.push_back(make_pair(stoi(items[i]), stoi(items[i + 1])));
+    }
+    alignments.push_back(alignment);
+  }
+  alignments.shrink_to_fit();
+}
+
+Alignment::Alignment() {}
+
+Alignment::~Alignment() {}
+
+vector<pair<int, int> > Alignment::GetLinks(int sentence_index) const {
+  return alignments[sentence_index];
+}
+
+void Alignment::WriteBinary(const fs::path& filepath) {
+  FILE* file = fopen(filepath.string().c_str(), "w");
+  int size = alignments.size();
+  fwrite(&size, sizeof(int), 1, file);
+  for (vector<pair<int, int> > alignment: alignments) {
+    size = alignment.size();
+    fwrite(&size, sizeof(int), 1, file);
+    fwrite(alignment.data(), sizeof(pair<int, int>), size, file);
+  }
+}
+
+} // namespace extractor
diff --git a/extractor/alignment.h b/extractor/alignment.h
new file mode 100644
index 00000000..e9292121
--- /dev/null
+++ b/extractor/alignment.h
@@ -0,0 +1,39 @@
+#ifndef _ALIGNMENT_H_
+#define _ALIGNMENT_H_
+
+#include <string>
+#include <vector>
+
+#include <boost/filesystem.hpp>
+
+namespace fs = boost::filesystem;
+using namespace std;
+
+namespace extractor {
+
+/**
+ * Data structure storing the word alignments for a parallel corpus.
+ */
+class Alignment {
+ public:
+  // Reads alignment from text file.
+  Alignment(const string& filename);
+
+  // Returns the alignment for a given sentence.
+  virtual vector<pair<int, int> > GetLinks(int sentence_index) const;
+
+  // Writes alignment to file in binary format.
+  void WriteBinary(const fs::path& filepath);
+
+  virtual ~Alignment();
+
+ protected:
+  Alignment();
+
+ private:
+  vector<vector<pair<int, int> > > alignments;
+};
+
+} // namespace extractor
+
+#endif
diff --git a/extractor/alignment_test.cc b/extractor/alignment_test.cc
new file mode 100644
index 00000000..a7defb66
--- /dev/null
+++ b/extractor/alignment_test.cc
@@ -0,0 +1,33 @@
+#include <gtest/gtest.h>
+
+#include <memory>
+#include <string>
+
+#include "alignment.h"
+
+using namespace std;
+using namespace ::testing;
+
+namespace extractor {
+namespace {
+
+class AlignmentTest : public Test {
+ protected:
+  virtual void SetUp() {
+    alignment = make_shared<Alignment>("sample_alignment.txt");
+  }
+
+  shared_ptr<Alignment> alignment;
+};
+
+TEST_F(AlignmentTest, TestGetLinks) {
+  vector<pair<int, int> > expected_links = {
+    make_pair(0, 0), make_pair(1, 1), make_pair(2, 2)
+  };
+  EXPECT_EQ(expected_links, alignment->GetLinks(0));
+  expected_links = {make_pair(1, 0), make_pair(2, 1)};
+  EXPECT_EQ(expected_links, alignment->GetLinks(1));
+}
+
+} // namespace
+} // namespace extractor
diff --git a/extractor/compile.cc b/extractor/compile.cc
new file mode 100644
index 00000000..a9ae2cef
--- /dev/null
+++ b/extractor/compile.cc
@@ -0,0 +1,100 @@
+#include <iostream>
+#include <string>
+
+#include <boost/filesystem.hpp>
+#include <boost/program_options.hpp>
+#include <boost/program_options/variables_map.hpp>
+
+#include "alignment.h"
+#include "data_array.h"
+#include "precomputation.h"
+#include "suffix_array.h"
+#include "translation_table.h"
+
+namespace fs = boost::filesystem;
+namespace po = boost::program_options;
+using namespace std;
+using namespace extractor;
+
+int main(int argc, char** argv) {
+  po::options_description desc("Command line options");
+  desc.add_options()
+    ("help,h", "Show available options")
+    ("source,f", po::value<string>(), "Source language corpus")
+    ("target,e", po::value<string>(), "Target language corpus")
+    ("bitext,b", po::value<string>(), "Parallel text (source ||| target)")
+    ("alignment,a", po::value<string>()->required(), "Bitext word alignment")
+    ("output,o", po::value<string>()->required(), "Output path")
+    ("frequent", po::value<int>()->default_value(100),
+        "Number of precomputed frequent patterns")
+    ("super_frequent", po::value<int>()->default_value(10),
+        "Number of precomputed super frequent patterns")
+    ("max_rule_span,s", po::value<int>()->default_value(15),
+        "Maximum rule span")
+    ("max_rule_symbols,l", po::value<int>()->default_value(5),
+        "Maximum number of symbols (terminals + nontermals) in a rule")
+    ("min_gap_size,g", po::value<int>()->default_value(1), "Minimum gap size")
+    ("max_phrase_len,p", po::value<int>()->default_value(4),
+        "Maximum frequent phrase length")
+    ("min_frequency", po::value<int>()->default_value(1000),
+        "Minimum number of occurrences for a pharse to be considered frequent");
+
+  po::variables_map vm;
+  po::store(po::parse_command_line(argc, argv, desc), vm);
+
+  // Check for help argument before notify, so we don't need to pass in the
+  // required parameters.
+  if (vm.count("help")) {
+    cout << desc << endl;
+    return 0;
+  }
+
+  po::notify(vm);
+
+  if (!((vm.count("source") && vm.count("target")) || vm.count("bitext"))) {
+    cerr << "A paralel corpus is required. "
+         << "Use -f (source) with -e (target) or -b (bitext)."
+         << endl;
+    return 1;
+  }
+
+  fs::path output_dir(vm["output"].as<string>().c_str());
+  if (!fs::exists(output_dir)) {
+    fs::create_directory(output_dir);
+  }
+
+  shared_ptr<DataArray> source_data_array, target_data_array;
+  if (vm.count("bitext")) {
+    source_data_array = make_shared<DataArray>(
+        vm["bitext"].as<string>(), SOURCE);
+    target_data_array = make_shared<DataArray>(
+        vm["bitext"].as<string>(), TARGET);
+  } else {
+    source_data_array = make_shared<DataArray>(vm["source"].as<string>());
+    target_data_array = make_shared<DataArray>(vm["target"].as<string>());
+  }
+  shared_ptr<SuffixArray> source_suffix_array =
+      make_shared<SuffixArray>(source_data_array);
+  source_suffix_array->WriteBinary(output_dir / fs::path("f.bin"));
+  target_data_array->WriteBinary(output_dir / fs::path("e.bin"));
+
+  shared_ptr<Alignment> alignment =
+      make_shared<Alignment>(vm["alignment"].as<string>());
+  alignment->WriteBinary(output_dir / fs::path("a.bin"));
+
+  Precomputation precomputation(
+      source_suffix_array,
+      vm["frequent"].as<int>(),
+      vm["super_frequent"].as<int>(),
+      vm["max_rule_span"].as<int>(),
+      vm["max_rule_symbols"].as<int>(),
+      vm["min_gap_size"].as<int>(),
+      vm["max_phrase_len"].as<int>(),
+      vm["min_frequency"].as<int>());
+  precomputation.WriteBinary(output_dir / fs::path("precompute.bin"));
+
+  TranslationTable table(source_data_array, target_data_array, alignment);
+  table.WriteBinary(output_dir / fs::path("lex.bin"));
+
+  return 0;
+}
diff --git a/extractor/data_array.cc b/extractor/data_array.cc
new file mode 100644
index 00000000..203fe219
--- /dev/null
+++ b/extractor/data_array.cc
@@ -0,0 +1,161 @@
+#include "data_array.h"
+
+#include <fstream>
+#include <iostream>
+#include <sstream>
+#include <string>
+
+#include <boost/filesystem.hpp>
+
+namespace fs = boost::filesystem;
+using namespace std;
+
+namespace extractor {
+
+int DataArray::NULL_WORD = 0;
+int DataArray::END_OF_LINE = 1;
+string DataArray::NULL_WORD_STR = "__NULL__";
+string DataArray::END_OF_LINE_STR = "__END_OF_LINE__";
+
+DataArray::DataArray() {
+  InitializeDataArray();
+}
+
+DataArray::DataArray(const string& filename) {
+  InitializeDataArray();
+  ifstream infile(filename.c_str());
+  vector<string> lines;
+  string line;
+  while (getline(infile, line)) {
+    lines.push_back(line);
+  }
+  CreateDataArray(lines);
+}
+
+DataArray::DataArray(const string& filename, const Side& side) {
+  InitializeDataArray();
+  ifstream infile(filename.c_str());
+  vector<string> lines;
+  string line, delimiter = "|||";
+  while (getline(infile, line)) {
+    int position = line.find(delimiter);
+    if (side == SOURCE) {
+      lines.push_back(line.substr(0, position));
+    } else {
+      lines.push_back(line.substr(position + delimiter.size()));
+    }
+  }
+  CreateDataArray(lines);
+}
+
+void DataArray::InitializeDataArray() {
+  word2id[NULL_WORD_STR] = NULL_WORD;
+  id2word.push_back(NULL_WORD_STR);
+  word2id[END_OF_LINE_STR] = END_OF_LINE;
+  id2word.push_back(END_OF_LINE_STR);
+}
+
+void DataArray::CreateDataArray(const vector<string>& lines) {
+  for (size_t i = 0; i < lines.size(); ++i) {
+    sentence_start.push_back(data.size());
+
+    istringstream iss(lines[i]);
+    string word;
+    while (iss >> word) {
+      if (word2id.count(word) == 0) {
+        word2id[word] = id2word.size();
+        id2word.push_back(word);
+      }
+      data.push_back(word2id[word]);
+      sentence_id.push_back(i);
+    }
+    data.push_back(END_OF_LINE);
+    sentence_id.push_back(i);
+  }
+  sentence_start.push_back(data.size());
+
+  data.shrink_to_fit();
+  sentence_id.shrink_to_fit();
+  sentence_start.shrink_to_fit();
+}
+
+DataArray::~DataArray() {}
+
+const vector<int>& DataArray::GetData() const {
+  return data;
+}
+
+int DataArray::AtIndex(int index) const {
+  return data[index];
+}
+
+string DataArray::GetWordAtIndex(int index) const {
+  return id2word[data[index]];
+}
+
+int DataArray::GetSize() const {
+  return data.size();
+}
+
+int DataArray::GetVocabularySize() const {
+  return id2word.size();
+}
+
+int DataArray::GetNumSentences() const {
+  return sentence_start.size() - 1;
+}
+
+int DataArray::GetSentenceStart(int position) const {
+  return sentence_start[position];
+}
+
+int DataArray::GetSentenceLength(int sentence_id) const {
+  // Ignore end of line markers.
+  return sentence_start[sentence_id + 1] - sentence_start[sentence_id] - 1;
+}
+
+int DataArray::GetSentenceId(int position) const {
+  return sentence_id[position];
+}
+
+void DataArray::WriteBinary(const fs::path& filepath) const {
+  std::cerr << "File: " << filepath.string() << std::endl;
+  WriteBinary(fopen(filepath.string().c_str(), "w"));
+}
+
+void DataArray::WriteBinary(FILE* file) const {
+  int size = id2word.size();
+  fwrite(&size, sizeof(int), 1, file);
+  for (string word: id2word) {
+    size = word.size();
+    fwrite(&size, sizeof(int), 1, file);
+    fwrite(word.data(), sizeof(char), size, file);
+  }
+
+  size = data.size();
+  fwrite(&size, sizeof(int), 1, file);
+  fwrite(data.data(), sizeof(int), size, file);
+
+  size = sentence_id.size();
+  fwrite(&size, sizeof(int), 1, file);
+  fwrite(sentence_id.data(), sizeof(int), size, file);
+
+  size = sentence_start.size();
+  fwrite(&size, sizeof(int), 1, file);
+  fwrite(sentence_start.data(), sizeof(int), 1, file);
+}
+
+bool DataArray::HasWord(const string& word) const {
+  return word2id.count(word);
+}
+
+int DataArray::GetWordId(const string& word) const {
+  auto result = word2id.find(word);
+  return result == word2id.end() ? -1 : result->second;
+}
+
+string DataArray::GetWord(int word_id) const {
+  return id2word[word_id];
+}
+
+} // namespace extractor
diff --git a/extractor/data_array.h b/extractor/data_array.h
new file mode 100644
index 00000000..978a6931
--- /dev/null
+++ b/extractor/data_array.h
@@ -0,0 +1,110 @@
+#ifndef _DATA_ARRAY_H_
+#define _DATA_ARRAY_H_
+
+#include <string>
+#include <unordered_map>
+#include <vector>
+
+#include <boost/filesystem.hpp>
+
+namespace fs = boost::filesystem;
+using namespace std;
+
+namespace extractor {
+
+enum Side {
+  SOURCE,
+  TARGET
+};
+
+/**
+ * Data structure storing information about a single side of a parallel corpus.
+ *
+ * Each word is mapped to a unique integer (word_id). The data structure holds
+ * the corpus in the numberized format, together with the hash table mapping
+ * words to word_ids. It also holds additional information such as the starting
+ * index for each sentence and, for each token, the index of the sentence it
+ * belongs to.
+ *
+ * Note: This class has features for both the source and target data arrays.
+ * Maybe we can save some memory by having more specific implementations (not
+ * likely to save a lot of memory tough).
+ */
+class DataArray {
+ public:
+  static int NULL_WORD;
+  static int END_OF_LINE;
+  static string NULL_WORD_STR;
+  static string END_OF_LINE_STR;
+
+  // Reads data array from text file.
+  DataArray(const string& filename);
+
+  // Reads data array from bitext file where the sentences are separated by |||.
+  DataArray(const string& filename, const Side& side);
+
+  virtual ~DataArray();
+
+  // Returns a vector containing the word ids.
+  virtual const vector<int>& GetData() const;
+
+  // Returns the word id at the specified position.
+  virtual int AtIndex(int index) const;
+
+  // Returns the original word at the specified position.
+  virtual string GetWordAtIndex(int index) const;
+
+  // Returns the size of the data array.
+  virtual int GetSize() const;
+
+  // Returns the number of distinct words in the data array.
+  virtual int GetVocabularySize() const;
+
+  // Returns whether a word has ever been observed in the data array.
+  virtual bool HasWord(const string& word) const;
+
+  // Returns the word id for a given word or -1 if it the word has never been
+  // observed.
+  virtual int GetWordId(const string& word) const;
+
+  // Returns the word corresponding to a particular word id.
+  virtual string GetWord(int word_id) const;
+
+  // Returns the number of sentences in the data.
+  virtual int GetNumSentences() const;
+
+  // Returns the index where the sentence containing the given position starts.
+  virtual int GetSentenceStart(int position) const;
+
+  // Returns the length of the sentence.
+  virtual int GetSentenceLength(int sentence_id) const;
+
+  // Returns the number of the sentence containing the given position.
+  virtual int GetSentenceId(int position) const;
+
+  // Writes data array to file in binary format.
+  void WriteBinary(const fs::path& filepath) const;
+
+  // Writes data array to file in binary format.
+  void WriteBinary(FILE* file) const;
+
+ protected:
+  DataArray();
+
+ private:
+  // Sets up specific constants.
+  void InitializeDataArray();
+
+  // Constructs the data array.
+  void CreateDataArray(const vector<string>& lines);
+
+  unordered_map<string, int> word2id;
+  vector<string> id2word;
+  vector<int> data;
+  vector<int> sentence_id;
+  vector<int> sentence_start;
+};
+
+} // namespace extractor
+
+#endif
diff --git a/extractor/data_array_test.cc b/extractor/data_array_test.cc
new file mode 100644
index 00000000..71175fda
--- /dev/null
+++ b/extractor/data_array_test.cc
@@ -0,0 +1,98 @@
+#include <gtest/gtest.h>
+
+#include <memory>
+#include <string>
+
+#include <boost/filesystem.hpp>
+
+#include "data_array.h"
+
+using namespace std;
+using namespace ::testing;
+namespace fs = boost::filesystem;
+
+namespace extractor {
+namespace {
+
+class DataArrayTest : public Test {
+ protected:
+  virtual void SetUp() {
+    string sample_test_file("sample_bitext.txt");
+    source_data = make_shared<DataArray>(sample_test_file, SOURCE);
+    target_data = make_shared<DataArray>(sample_test_file, TARGET);
+  }
+
+  shared_ptr<DataArray> source_data;
+  shared_ptr<DataArray> target_data;
+};
+
+TEST_F(DataArrayTest, TestGetData) {
+  vector<int> expected_source_data = {2, 3, 4, 5, 1, 2, 6, 7, 8, 5, 1};
+  vector<string> expected_source_words = {
+      "ana", "are", "mere", ".", "__END_OF_LINE__",
+      "ana", "bea", "mult", "lapte", ".", "__END_OF_LINE__"
+  };
+  EXPECT_EQ(expected_source_data, source_data->GetData());
+  EXPECT_EQ(expected_source_data.size(), source_data->GetSize());
+  for (size_t i = 0; i < expected_source_data.size(); ++i) {
+    EXPECT_EQ(expected_source_data[i], source_data->AtIndex(i));
+    EXPECT_EQ(expected_source_words[i], source_data->GetWordAtIndex(i));
+  }
+
+  vector<int> expected_target_data = {2, 3, 4, 5, 1, 2, 6, 7, 8, 9, 10, 5, 1};
+  vector<string> expected_target_words = {
+      "anna", "has", "apples", ".", "__END_OF_LINE__",
+      "anna", "drinks", "a", "lot", "of", "milk", ".", "__END_OF_LINE__"
+  };
+  EXPECT_EQ(expected_target_data, target_data->GetData());
+  EXPECT_EQ(expected_target_data.size(), target_data->GetSize());
+  for (size_t i = 0; i < expected_target_data.size(); ++i) {
+    EXPECT_EQ(expected_target_data[i], target_data->AtIndex(i));
+    EXPECT_EQ(expected_target_words[i], target_data->GetWordAtIndex(i));
+  }
+}
+
+TEST_F(DataArrayTest, TestVocabulary) {
+  EXPECT_EQ(9, source_data->GetVocabularySize());
+  EXPECT_TRUE(source_data->HasWord("mere"));
+  EXPECT_EQ(4, source_data->GetWordId("mere"));
+  EXPECT_EQ("mere", source_data->GetWord(4));
+  EXPECT_FALSE(source_data->HasWord("banane"));
+
+  EXPECT_EQ(11, target_data->GetVocabularySize());
+  EXPECT_TRUE(target_data->HasWord("apples"));
+  EXPECT_EQ(4, target_data->GetWordId("apples"));
+  EXPECT_EQ("apples", target_data->GetWord(4));
+  EXPECT_FALSE(target_data->HasWord("bananas"));
+}
+
+TEST_F(DataArrayTest, TestSentenceData) {
+  EXPECT_EQ(2, source_data->GetNumSentences());
+  EXPECT_EQ(0, source_data->GetSentenceStart(0));
+  EXPECT_EQ(5, source_data->GetSentenceStart(1));
+  EXPECT_EQ(11, source_data->GetSentenceStart(2));
+
+  EXPECT_EQ(4, source_data->GetSentenceLength(0));
+  EXPECT_EQ(5, source_data->GetSentenceLength(1));
+
+  vector<int> expected_source_ids = {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1};
+  for (size_t i = 0; i < expected_source_ids.size(); ++i) {
+    EXPECT_EQ(expected_source_ids[i], source_data->GetSentenceId(i));
+  }
+
+  EXPECT_EQ(2, target_data->GetNumSentences());
+  EXPECT_EQ(0, target_data->GetSentenceStart(0));
+  EXPECT_EQ(5, target_data->GetSentenceStart(1));
+  EXPECT_EQ(13, target_data->GetSentenceStart(2));
+
+  EXPECT_EQ(4, target_data->GetSentenceLength(0));
+  EXPECT_EQ(7, target_data->GetSentenceLength(1));
+
+  vector<int> expected_target_ids = {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1};
+  for (size_t i = 0; i < expected_target_ids.size(); ++i) {
+    EXPECT_EQ(expected_target_ids[i], target_data->GetSentenceId(i));
+  }
+}
+
+} // namespace
+} // namespace extractor
diff --git a/extractor/fast_intersector.cc b/extractor/fast_intersector.cc
new file mode 100644
index 00000000..2a7693b2
--- /dev/null
+++ b/extractor/fast_intersector.cc
@@ -0,0 +1,195 @@
+#include "fast_intersector.h"
+
+#include <cassert>
+
+#include "data_array.h"
+#include "phrase.h"
+#include "phrase_location.h"
+#include "precomputation.h"
+#include "suffix_array.h"
+#include "vocabulary.h"
+
+namespace extractor {
+
+FastIntersector::FastIntersector(shared_ptr<SuffixArray> suffix_array,
+                                 shared_ptr<Precomputation> precomputation,
+                                 shared_ptr<Vocabulary> vocabulary,
+                                 int max_rule_span,
+                                 int min_gap_size) :
+    suffix_array(suffix_array),
+    vocabulary(vocabulary),
+    max_rule_span(max_rule_span),
+    min_gap_size(min_gap_size) {
+  Index precomputed_collocations = precomputation->GetCollocations();
+  for (pair<vector<int>, vector<int> > entry: precomputed_collocations) {
+    vector<int> phrase = ConvertPhrase(entry.first);
+    collocations[phrase] = entry.second;
+  }
+}
+
+FastIntersector::FastIntersector() {}
+
+FastIntersector::~FastIntersector() {}
+
+vector<int> FastIntersector::ConvertPhrase(const vector<int>& old_phrase) {
+  vector<int> new_phrase;
+  new_phrase.reserve(old_phrase.size());
+  shared_ptr<DataArray> data_array = suffix_array->GetData();
+  for (int word_id: old_phrase) {
+    if (word_id < 0) {
+      new_phrase.push_back(word_id);
+    } else {
+      new_phrase.push_back(
+          vocabulary->GetTerminalIndex(data_array->GetWord(word_id)));
+    }
+  }
+  return new_phrase;
+}
+
+PhraseLocation FastIntersector::Intersect(
+    PhraseLocation& prefix_location,
+    PhraseLocation& suffix_location,
+    const Phrase& phrase) {
+  vector<int> symbols = phrase.Get();
+
+  // We should never attempt to do an intersect query for a pattern starting or
+  // ending with a non terminal. The RuleFactory should handle these cases,
+  // initializing the matchings list with the one for the pattern without the
+  // starting or ending terminal.
+  assert(vocabulary->IsTerminal(symbols.front())
+      && vocabulary->IsTerminal(symbols.back()));
+
+  if (collocations.count(symbols)) {
+    return PhraseLocation(collocations[symbols], phrase.Arity() + 1);
+  }
+
+  bool prefix_ends_with_x =
+      !vocabulary->IsTerminal(symbols[symbols.size() - 2]);
+  bool suffix_starts_with_x = !vocabulary->IsTerminal(symbols[1]);
+  if (EstimateNumOperations(prefix_location, prefix_ends_with_x) <=
+      EstimateNumOperations(suffix_location, suffix_starts_with_x)) {
+    return ExtendPrefixPhraseLocation(prefix_location, phrase,
+                                      prefix_ends_with_x, symbols.back());
+  } else {
+    return ExtendSuffixPhraseLocation(suffix_location, phrase,
+                                      suffix_starts_with_x, symbols.front());
+  }
+}
+
+int FastIntersector::EstimateNumOperations(
+    const PhraseLocation& phrase_location, bool has_margin_x) const {
+  int num_locations = phrase_location.GetSize();
+  return has_margin_x ? num_locations * max_rule_span : num_locations;
+}
+
+PhraseLocation FastIntersector::ExtendPrefixPhraseLocation(
+    PhraseLocation& prefix_location, const Phrase& phrase,
+    bool prefix_ends_with_x, int next_symbol) const {
+  ExtendPhraseLocation(prefix_location);
+  vector<int> positions = *prefix_location.matchings;
+  int num_subpatterns = prefix_location.num_subpatterns;
+
+  vector<int> new_positions;
+  shared_ptr<DataArray> data_array = suffix_array->GetData();
+  int data_array_symbol = data_array->GetWordId(
+      vocabulary->GetTerminalValue(next_symbol));
+  if (data_array_symbol == -1) {
+    return PhraseLocation(new_positions, num_subpatterns);
+  }
+
+  pair<int, int> range = GetSearchRange(prefix_ends_with_x);
+  for (size_t i = 0; i < positions.size(); i += num_subpatterns) {
+    int sent_id = data_array->GetSentenceId(positions[i]);
+    int sent_end = data_array->GetSentenceStart(sent_id + 1) - 1;
+    int pattern_end = positions[i + num_subpatterns - 1] + range.first;
+    if (prefix_ends_with_x) {
+      pattern_end += phrase.GetChunkLen(phrase.Arity() - 1) - 1;
+    } else {
+      pattern_end += phrase.GetChunkLen(phrase.Arity()) - 2;
+    }
+    // Searches for the last symbol in the phrase after each prefix occurrence.
+    for (int j = range.first; j < range.second; ++j) {
+      if (pattern_end >= sent_end ||
+          pattern_end - positions[i] >= max_rule_span) {
+        break;
+      }
+
+      if (data_array->AtIndex(pattern_end) == data_array_symbol) {
+        new_positions.insert(new_positions.end(), positions.begin() + i,
+                             positions.begin() + i + num_subpatterns);
+        if (prefix_ends_with_x) {
+          new_positions.push_back(pattern_end);
+        }
+      }
+      ++pattern_end;
+    }
+  }
+
+  return PhraseLocation(new_positions, phrase.Arity() + 1);
+}
+
+PhraseLocation FastIntersector::ExtendSuffixPhraseLocation(
+    PhraseLocation& suffix_location, const Phrase& phrase,
+    bool suffix_starts_with_x, int prev_symbol) const {
+  ExtendPhraseLocation(suffix_location);
+  vector<int> positions = *suffix_location.matchings;
+  int num_subpatterns = suffix_location.num_subpatterns;
+
+  vector<int> new_positions;
+  shared_ptr<DataArray> data_array = suffix_array->GetData();
+  int data_array_symbol = data_array->GetWordId(
+      vocabulary->GetTerminalValue(prev_symbol));
+  if (data_array_symbol == -1) {
+    return PhraseLocation(new_positions, num_subpatterns);
+  }
+
+  pair<int, int> range = GetSearchRange(suffix_starts_with_x);
+  for (size_t i = 0; i < positions.size(); i += num_subpatterns) {
+    int sent_id = data_array->GetSentenceId(positions[i]);
+    int sent_start = data_array->GetSentenceStart(sent_id);
+    int pattern_start = positions[i] - range.first;
+    int pattern_end = positions[i + num_subpatterns - 1] +
+        phrase.GetChunkLen(phrase.Arity()) - 1;
+    // Searches for the first symbol in the phrase before each suffix
+    // occurrence.
+    for (int j = range.first; j < range.second; ++j) {
+      if (pattern_start < sent_start ||
+          pattern_end - pattern_start >= max_rule_span) {
+        break;
+      }
+
+      if (data_array->AtIndex(pattern_start) == data_array_symbol) {
+        new_positions.push_back(pattern_start);
+        new_positions.insert(new_positions.end(),
+                             positions.begin() + i + !suffix_starts_with_x,
+                             positions.begin() + i + num_subpatterns);
+      }
+      --pattern_start;
+    }
+  }
+
+  return PhraseLocation(new_positions, phrase.Arity() + 1);
+}
+
+void FastIntersector::ExtendPhraseLocation(PhraseLocation& location) const {
+  if (location.matchings != NULL) {
+    return;
+  }
+
+  location.num_subpatterns = 1;
+  location.matchings = make_shared<vector<int> >();
+  for (int i = location.sa_low; i < location.sa_high; ++i) {
+    location.matchings->push_back(suffix_array->GetSuffix(i));
+  }
+  location.sa_low = location.sa_high = 0;
+}
+
+pair<int, int> FastIntersector::GetSearchRange(bool has_marginal_x) const {
+  if (has_marginal_x) {
+    return make_pair(min_gap_size + 1, max_rule_span);
+  } else {
+    return make_pair(1, 2);
+  }
+}
+
+} // namespace extractor
diff --git a/extractor/fast_intersector.h b/extractor/fast_intersector.h
new file mode 100644
index 00000000..f950a2a9
--- /dev/null
+++ b/extractor/fast_intersector.h
@@ -0,0 +1,96 @@
+#ifndef _FAST_INTERSECTOR_H_
+#define _FAST_INTERSECTOR_H_
+
+#include <memory>
+#include <unordered_map>
+#include <vector>
+
+#include <boost/functional/hash.hpp>
+
+using namespace std;
+
+namespace extractor {
+
+typedef boost::hash<vector<int> > VectorHash;
+typedef unordered_map<vector<int>, vector<int>, VectorHash> Index;
+
+class Phrase;
+class PhraseLocation;
+class Precomputation;
+class SuffixArray;
+class Vocabulary;
+
+/**
+ * Component for searching the training data for occurrences of source phrases
+ * containing nonterminals
+ *
+ * Given a source phrase containing a nonterminal, we first query the
+ * precomputed index containing frequent collocations. If the phrase is not
+ * frequent enough, we extend the matchings of either its prefix or its suffix,
+ * depending on which operation seems to require less computations.
+ *
+ * Note: This method for intersecting phrase locations is faster than both
+ * mergers (linear or Baeza Yates) described in Adam Lopez' dissertation.
+ */
+class FastIntersector {
+ public:
+  FastIntersector(shared_ptr<SuffixArray> suffix_array,
+                  shared_ptr<Precomputation> precomputation,
+                  shared_ptr<Vocabulary> vocabulary,
+                  int max_rule_span,
+                  int min_gap_size);
+
+  virtual ~FastIntersector();
+
+  // Finds the locations of a phrase given the locations of its prefix and
+  // suffix.
+  virtual PhraseLocation Intersect(PhraseLocation& prefix_location,
+                                   PhraseLocation& suffix_location,
+                                   const Phrase& phrase);
+
+ protected:
+  FastIntersector();
+
+ private:
+  // Uses the vocabulary to convert the phrase from the numberized format
+  // specified by the source data array to the numberized format given by the
+  // vocabulary.
+  vector<int> ConvertPhrase(const vector<int>& old_phrase);
+
+  // Estimates the number of computations needed if the prefix/suffix is
+  // extended. If the last/first symbol is separated from the rest of the phrase
+  // by a nonterminal, then for each occurrence of the prefix/suffix we need to
+  // check max_rule_span positions. Otherwise, we only need to check a single
+  // position for each occurrence.
+  int EstimateNumOperations(const PhraseLocation& phrase_location,
+                            bool has_margin_x) const;
+
+  // Uses the occurrences of the prefix to find the occurrences of the phrase.
+  PhraseLocation ExtendPrefixPhraseLocation(PhraseLocation& prefix_location,
+                                            const Phrase& phrase,
+                                            bool prefix_ends_with_x,
+                                            int next_symbol) const;
+
+  // Uses the occurrences of the suffix to find the occurrences of the phrase.
+  PhraseLocation ExtendSuffixPhraseLocation(PhraseLocation& suffix_location,
+                                            const Phrase& phrase,
+                                            bool suffix_starts_with_x,
+                                            int prev_symbol) const;
+
+  // Extends the prefix/suffix location to a list of subpatterns positions if it
+  // represents a suffix array range.
+  void ExtendPhraseLocation(PhraseLocation& location) const;
+
+  // Returns the range in which the search should be performed.
+  pair<int, int> GetSearchRange(bool has_marginal_x) const;
+
+  shared_ptr<SuffixArray> suffix_array;
+  shared_ptr<Vocabulary> vocabulary;
+  int max_rule_span;
+  int min_gap_size;
+  Index collocations;
+};
+
+} // namespace extractor
+
+#endif
diff --git a/extractor/fast_intersector_test.cc b/extractor/fast_intersector_test.cc
new file mode 100644
index 00000000..76c3aaea
--- /dev/null
+++ b/extractor/fast_intersector_test.cc
@@ -0,0 +1,146 @@
+#include <gtest/gtest.h>
+
+#include <memory>
+
+#include "fast_intersector.h"
+#include "mocks/mock_data_array.h"
+#include "mocks/mock_precomputation.h"
+#include "mocks/mock_suffix_array.h"
+#include "mocks/mock_vocabulary.h"
+#include "phrase.h"
+#include "phrase_location.h"
+#include "phrase_builder.h"
+
+using namespace std;
+using namespace ::testing;
+
+namespace extractor {
+namespace {
+
+class FastIntersectorTest : public Test {
+ protected:
+  virtual void SetUp() {
+    vector<string> words = {"EOL", "it", "makes", "him", "and", "mars", ",",
+                            "sets", "on", "takes", "off", "."};
+    vocabulary = make_shared<MockVocabulary>();
+    for (size_t i = 0; i < words.size(); ++i) {
+      EXPECT_CALL(*vocabulary, GetTerminalIndex(words[i]))
+          .WillRepeatedly(Return(i));
+      EXPECT_CALL(*vocabulary, GetTerminalValue(i))
+          .WillRepeatedly(Return(words[i]));
+    }
+
+    vector<int> data = {1, 2, 3, 4, 1, 5, 3, 6, 1,
+                        7, 3, 8, 4, 1, 9, 3, 10, 11, 0};
+    data_array = make_shared<MockDataArray>();
+    for (size_t i = 0; i < data.size(); ++i) {
+      EXPECT_CALL(*data_array, AtIndex(i)).WillRepeatedly(Return(data[i]));
+      EXPECT_CALL(*data_array, GetSentenceId(i))
+          .WillRepeatedly(Return(0));
+    }
+    EXPECT_CALL(*data_array, GetSentenceStart(0))
+        .WillRepeatedly(Return(0));
+    EXPECT_CALL(*data_array, GetSentenceStart(1))
+        .WillRepeatedly(Return(19));
+    for (size_t i = 0; i < words.size(); ++i) {
+      EXPECT_CALL(*data_array, GetWordId(words[i]))
+          .WillRepeatedly(Return(i));
+      EXPECT_CALL(*data_array, GetWord(i))
+          .WillRepeatedly(Return(words[i]));
+    }
+
+    vector<int> suffixes = {18, 0, 4, 8, 13, 1, 2, 6, 10, 15, 3, 12, 5, 7, 9,
+                            11, 14, 16, 17};
+    suffix_array = make_shared<MockSuffixArray>();
+    EXPECT_CALL(*suffix_array, GetData()).WillRepeatedly(Return(data_array));
+    for (size_t i = 0; i < suffixes.size(); ++i) {
+      EXPECT_CALL(*suffix_array, GetSuffix(i)).
+          WillRepeatedly(Return(suffixes[i]));
+    }
+
+    precomputation = make_shared<MockPrecomputation>();
+    EXPECT_CALL(*precomputation, GetCollocations())
+        .WillRepeatedly(ReturnRef(collocations));
+
+    phrase_builder = make_shared<PhraseBuilder>(vocabulary);
+    intersector = make_shared<FastIntersector>(suffix_array, precomputation,
+                                               vocabulary, 15, 1);
+  }
+
+  Index collocations;
+  shared_ptr<MockDataArray> data_array;
+  shared_ptr<MockSuffixArray> suffix_array;
+  shared_ptr<MockPrecomputation> precomputation;
+  shared_ptr<MockVocabulary> vocabulary;
+  shared_ptr<FastIntersector> intersector;
+  shared_ptr<PhraseBuilder> phrase_builder;
+};
+
+TEST_F(FastIntersectorTest, TestCachedCollocation) {
+  vector<int> symbols = {8, -1, 9};
+  vector<int> expected_location = {11};
+  Phrase phrase = phrase_builder->Build(symbols);
+  PhraseLocation prefix_location(15, 16), suffix_location(16, 17);
+
+  collocations[symbols] = expected_location;
+  EXPECT_CALL(*precomputation, GetCollocations())
+      .WillRepeatedly(ReturnRef(collocations));
+  intersector = make_shared<FastIntersector>(suffix_array, precomputation,
+                                             vocabulary, 15, 1);
+
+  PhraseLocation result = intersector->Intersect(
+      prefix_location, suffix_location, phrase);
+
+  EXPECT_EQ(PhraseLocation(expected_location, 2), result);
+  EXPECT_EQ(PhraseLocation(15, 16), prefix_location);
+  EXPECT_EQ(PhraseLocation(16, 17), suffix_location);
+}
+
+TEST_F(FastIntersectorTest, TestIntersectaXbXcExtendSuffix) {
+  vector<int> symbols = {1, -1, 3, -1, 1};
+  Phrase phrase = phrase_builder->Build(symbols);
+  vector<int> prefix_locs = {0, 2, 0, 6, 0, 10, 4, 6, 4, 10, 4, 15, 8, 10,
+                             8, 15, 3, 15};
+  vector<int> suffix_locs = {2, 4, 2, 8, 2, 13, 6, 8, 6, 13, 10, 13};
+  PhraseLocation prefix_location(prefix_locs, 2);
+  PhraseLocation suffix_location(suffix_locs, 2);
+
+  vector<int> expected_locs = {0, 2, 4, 0, 2, 8, 0, 2, 13, 4, 6, 8, 0, 6, 8,
+                               4, 6, 13, 0, 6, 13, 8, 10, 13, 4, 10, 13,
+                               0, 10, 13};
+  PhraseLocation result = intersector->Intersect(
+      prefix_location, suffix_location, phrase);
+  EXPECT_EQ(PhraseLocation(expected_locs, 3), result);
+}
+
+TEST_F(FastIntersectorTest, TestIntersectaXbExtendPrefix) {
+  vector<int> symbols = {1, -1, 3};
+  Phrase phrase = phrase_builder->Build(symbols);
+  PhraseLocation prefix_location(1, 5), suffix_location(6, 10);
+
+  vector<int> expected_prefix_locs = {0, 4, 8, 13};
+  vector<int> expected_locs = {0, 2, 0, 6, 0, 10, 4, 6, 4, 10, 4, 15, 8, 10,
+                               8, 15, 13, 15};
+  PhraseLocation result = intersector->Intersect(
+      prefix_location, suffix_location, phrase);
+  EXPECT_EQ(PhraseLocation(expected_locs, 2), result);
+  EXPECT_EQ(PhraseLocation(expected_prefix_locs, 1), prefix_location);
+}
+
+TEST_F(FastIntersectorTest, TestIntersectCheckEstimates) {
+  // The suffix matches in fewer positions, but because it starts with an X
+  // it requires more operations and we prefer extending the prefix.
+  vector<int> symbols = {1, -1, 4, 1};
+  Phrase phrase = phrase_builder->Build(symbols);
+  vector<int> prefix_locs = {0, 3, 0, 12, 4, 12, 8, 12};
+  PhraseLocation prefix_location(prefix_locs, 2), suffix_location(10, 12);
+
+  vector<int> expected_locs = {0, 3, 0, 12, 4, 12, 8, 12};
+  PhraseLocation result = intersector->Intersect(
+      prefix_location, suffix_location, phrase);
+  EXPECT_EQ(PhraseLocation(expected_locs, 2), result);
+  EXPECT_EQ(PhraseLocation(10, 12), suffix_location);
+}
+
+} // namespace
+} // namespace extractor
diff --git a/extractor/features/count_source_target.cc b/extractor/features/count_source_target.cc
new file mode 100644
index 00000000..db0385e0
--- /dev/null
+++ b/extractor/features/count_source_target.cc
@@ -0,0 +1,17 @@
+#include "count_source_target.h"
+
+#include <cmath>
+
+namespace extractor {
+namespace features {
+
+double CountSourceTarget::Score(const FeatureContext& context) const {
+  return log10(1 + context.pair_count);
+}
+
+string CountSourceTarget::GetName() const {
+  return "CountEF";
+}
+
+} // namespace features
+} // namespace extractor
diff --git a/extractor/features/count_source_target.h b/extractor/features/count_source_target.h
new file mode 100644
index 00000000..8747fa60
--- /dev/null
+++ b/extractor/features/count_source_target.h
@@ -0,0 +1,22 @@
+#ifndef _COUNT_SOURCE_TARGET_H_
+#define _COUNT_SOURCE_TARGET_H_
+
+#include "feature.h"
+
+namespace extractor {
+namespace features {
+
+/**
+ * Feature for the number of times a word pair was found in the bitext.
+ */
+class CountSourceTarget : public Feature {
+ public:
+  double Score(const FeatureContext& context) const;
+
+  string GetName() const;
+};
+
+} // namespace features
+} // namespace extractor
+
+#endif
diff --git a/extractor/features/count_source_target_test.cc b/extractor/features/count_source_target_test.cc
new file mode 100644
index 00000000..1fd0c2aa
--- /dev/null
+++ b/extractor/features/count_source_target_test.cc
@@ -0,0 +1,36 @@
+#include <gtest/gtest.h>
+
+#include <memory>
+#include <string>
+
+#include "count_source_target.h"
+
+using namespace std;
+using namespace ::testing;
+
+namespace extractor {
+namespace features {
+namespace {
+
+class CountSourceTargetTest : public Test {
+ protected:
+  virtual void SetUp() {
+    feature = make_shared<CountSourceTarget>();
+  }
+
+  shared_ptr<CountSourceTarget> feature;
+};
+
+TEST_F(CountSourceTargetTest, TestGetName) {
+  EXPECT_EQ("CountEF", feature->GetName());
+}
+
+TEST_F(CountSourceTargetTest, TestScore) {
+  Phrase phrase;
+  FeatureContext context(phrase, phrase, 0.5, 9, 13);
+  EXPECT_EQ(1.0, feature->Score(context));
+}
+
+} // namespace
+} // namespace features
+} // namespace extractor
diff --git a/extractor/features/feature.cc b/extractor/features/feature.cc
new file mode 100644
index 00000000..939bcc59
--- /dev/null
+++ b/extractor/features/feature.cc
@@ -0,0 +1,11 @@
+#include "feature.h"
+
+namespace extractor {
+namespace features {
+
+const double Feature::MAX_SCORE = 99.0;
+
+Feature::~Feature() {}
+
+} // namespace features
+} // namespace extractor
diff --git a/extractor/features/feature.h b/extractor/features/feature.h
new file mode 100644
index 00000000..36ea504a
--- /dev/null
+++ b/extractor/features/feature.h
@@ -0,0 +1,47 @@
+#ifndef _FEATURE_H_
+#define _FEATURE_H_
+
+#include <string>
+
+#include "phrase.h"
+
+using namespace std;
+
+namespace extractor {
+namespace features {
+
+/**
+ * Structure providing context for computing feature scores.
+ */
+struct FeatureContext {
+  FeatureContext(const Phrase& source_phrase, const Phrase& target_phrase,
+                 double source_phrase_count, int pair_count, int num_samples) :
+    source_phrase(source_phrase), target_phrase(target_phrase),
+    source_phrase_count(source_phrase_count), pair_count(pair_count),
+    num_samples(num_samples) {}
+
+  Phrase source_phrase;
+  Phrase target_phrase;
+  double source_phrase_count;
+  int pair_count;
+  int num_samples;
+};
+
+/**
+ * Base class for features.
+ */
+class Feature {
+ public:
+  virtual double Score(const FeatureContext& context) const = 0;
+
+  virtual string GetName() const = 0;
+
+  virtual ~Feature();
+
+  static const double MAX_SCORE;
+};
+
+} // namespace features
+} // namespace extractor
+
+#endif
diff --git a/extractor/features/is_source_singleton.cc b/extractor/features/is_source_singleton.cc
new file mode 100644
index 00000000..1abb486f
--- /dev/null
+++ b/extractor/features/is_source_singleton.cc
@@ -0,0 +1,17 @@
+#include "is_source_singleton.h"
+
+#include <cmath>
+
+namespace extractor {
+namespace features {
+
+double IsSourceSingleton::Score(const FeatureContext& context) const {
+  return fabs(context.source_phrase_count - 1) < 1e-6;
+}
+
+string IsSourceSingleton::GetName() const {
+  return "IsSingletonF";
+}
+
+} // namespace features
+} // namespace extractor
diff --git a/extractor/features/is_source_singleton.h b/extractor/features/is_source_singleton.h
new file mode 100644
index 00000000..b8352d0e
--- /dev/null
+++ b/extractor/features/is_source_singleton.h
@@ -0,0 +1,22 @@
+#ifndef _IS_SOURCE_SINGLETON_H_
+#define _IS_SOURCE_SINGLETON_H_
+
+#include "feature.h"
+
+namespace extractor {
+namespace features {
+
+/**
+ * Boolean feature checking if the source phrase occurs only once in the data.
+ */
+class IsSourceSingleton : public Feature {
+ public:
+  double Score(const FeatureContext& context) const;
+
+  string GetName() const;
+};
+
+} // namespace features
+} // namespace extractor
+
+#endif
diff --git a/extractor/features/is_source_singleton_test.cc b/extractor/features/is_source_singleton_test.cc
new file mode 100644
index 00000000..f4266671
--- /dev/null
+++ b/extractor/features/is_source_singleton_test.cc
@@ -0,0 +1,39 @@
+#include <gtest/gtest.h>
+
+#include <memory>
+#include <string>
+
+#include "is_source_singleton.h"
+
+using namespace std;
+using namespace ::testing;
+
+namespace extractor {
+namespace features {
+namespace {
+
+class IsSourceSingletonTest : public Test {
+ protected:
+  virtual void SetUp() {
+    feature = make_shared<IsSourceSingleton>();
+  }
+
+  shared_ptr<IsSourceSingleton> feature;
+};
+
+TEST_F(IsSourceSingletonTest, TestGetName) {
+  EXPECT_EQ("IsSingletonF", feature->GetName());
+}
+
+TEST_F(IsSourceSingletonTest, TestScore) {
+  Phrase phrase;
+  FeatureContext context(phrase, phrase, 0.5, 3, 31);
+  EXPECT_EQ(0, feature->Score(context));
+
+  context = FeatureContext(phrase, phrase, 1, 3, 25);
+  EXPECT_EQ(1, feature->Score(context));
+}
+
+} // namespace
+} // namespace features
+} // namespace extractor
diff --git a/extractor/features/is_source_target_singleton.cc b/extractor/features/is_source_target_singleton.cc
new file mode 100644
index 00000000..03b3c62c
--- /dev/null
+++ b/extractor/features/is_source_target_singleton.cc
@@ -0,0 +1,17 @@
+#include "is_source_target_singleton.h"
+
+#include <cmath>
+
+namespace extractor {
+namespace features {
+
+double IsSourceTargetSingleton::Score(const FeatureContext& context) const {
+  return context.pair_count == 1;
+}
+
+string IsSourceTargetSingleton::GetName() const {
+  return "IsSingletonFE";
+}
+
+} // namespace features
+} // namespace extractor
diff --git a/extractor/features/is_source_target_singleton.h b/extractor/features/is_source_target_singleton.h
new file mode 100644
index 00000000..dacfebba
--- /dev/null
+++ b/extractor/features/is_source_target_singleton.h
@@ -0,0 +1,22 @@
+#ifndef _IS_SOURCE_TARGET_SINGLETON_H_
+#define _IS_SOURCE_TARGET_SINGLETON_H_
+
+#include "feature.h"
+
+namespace extractor {
+namespace features {
+
+/**
+ * Boolean feature checking if the phrase pair occurs only once in the data.
+ */
+class IsSourceTargetSingleton : public Feature {
+ public:
+  double Score(const FeatureContext& context) const;
+
+  string GetName() const;
+};
+
+} // namespace features
+} // namespace extractor
+
+#endif
diff --git a/extractor/features/is_source_target_singleton_test.cc b/extractor/features/is_source_target_singleton_test.cc
new file mode 100644
index 00000000..929635b0
--- /dev/null
+++ b/extractor/features/is_source_target_singleton_test.cc
@@ -0,0 +1,39 @@
+#include <gtest/gtest.h>
+
+#include <memory>
+#include <string>
+
+#include "is_source_target_singleton.h"
+
+using namespace std;
+using namespace ::testing;
+
+namespace extractor {
+namespace features {
+namespace {
+
+class IsSourceTargetSingletonTest : public Test {
+ protected:
+  virtual void SetUp() {
+    feature = make_shared<IsSourceTargetSingleton>();
+  }
+
+  shared_ptr<IsSourceTargetSingleton> feature;
+};
+
+TEST_F(IsSourceTargetSingletonTest, TestGetName) {
+  EXPECT_EQ("IsSingletonFE", feature->GetName());
+}
+
+TEST_F(IsSourceTargetSingletonTest, TestScore) {
+  Phrase phrase;
+  FeatureContext context(phrase, phrase, 0.5, 3, 7);
+  EXPECT_EQ(0, feature->Score(context));
+
+  context = FeatureContext(phrase, phrase, 2.3, 1, 28);
+  EXPECT_EQ(1, feature->Score(context));
+}
+
+} // namespace
+} // namespace features
+} // namespace extractor
diff --git a/extractor/features/max_lex_source_given_target.cc b/extractor/features/max_lex_source_given_target.cc
new file mode 100644
index 00000000..65d0ec68
--- /dev/null
+++ b/extractor/features/max_lex_source_given_target.cc
@@ -0,0 +1,37 @@
+#include "max_lex_source_given_target.h"
+
+#include <cmath>
+
+#include "data_array.h"
+#include "translation_table.h"
+
+namespace extractor {
+namespace features {
+
+MaxLexSourceGivenTarget::MaxLexSourceGivenTarget(
+    shared_ptr<TranslationTable> table) :
+    table(table) {}
+
+double MaxLexSourceGivenTarget::Score(const FeatureContext& context) const {
+  vector<string> source_words = context.source_phrase.GetWords();
+  vector<string> target_words = context.target_phrase.GetWords();
+  target_words.push_back(DataArray::NULL_WORD_STR);
+
+  double score = 0;
+  for (string source_word: source_words) {
+    double max_score = 0;
+    for (string target_word: target_words) {
+      max_score = max(max_score,
+          table->GetSourceGivenTargetScore(source_word, target_word));
+    }
+    score += max_score > 0 ? -log10(max_score) : MAX_SCORE;
+  }
+  return score;
+}
+
+string MaxLexSourceGivenTarget::GetName() const {
+  return "MaxLexFgivenE";
+}
+
+} // namespace features
+} // namespace extractor
diff --git a/extractor/features/max_lex_source_given_target.h b/extractor/features/max_lex_source_given_target.h
new file mode 100644
index 00000000..461b0ebf
--- /dev/null
+++ b/extractor/features/max_lex_source_given_target.h
@@ -0,0 +1,34 @@
+#ifndef _MAX_LEX_SOURCE_GIVEN_TARGET_H_
+#define _MAX_LEX_SOURCE_GIVEN_TARGET_H_
+
+#include <memory>
+
+#include "feature.h"
+
+using namespace std;
+
+namespace extractor {
+
+class TranslationTable;
+
+namespace features {
+
+/**
+ * Feature computing max(p(f | e)) across all pairs of words in the phrase pair.
+ */
+class MaxLexSourceGivenTarget : public Feature {
+ public:
+  MaxLexSourceGivenTarget(shared_ptr<TranslationTable> table);
+
+  double Score(const FeatureContext& context) const;
+
+  string GetName() const;
+
+ private:
+  shared_ptr<TranslationTable> table;
+};
+
+} // namespace features
+} // namespace extractor
+
+#endif
diff --git a/extractor/features/max_lex_source_given_target_test.cc b/extractor/features/max_lex_source_given_target_test.cc
new file mode 100644
index 00000000..7f6aae41
--- /dev/null
+++ b/extractor/features/max_lex_source_given_target_test.cc
@@ -0,0 +1,78 @@
+#include <gtest/gtest.h>
+
+#include <cmath>
+#include <memory>
+#include <string>
+
+#include "data_array.h"
+#include "mocks/mock_translation_table.h"
+#include "mocks/mock_vocabulary.h"
+#include "phrase_builder.h"
+#include "max_lex_source_given_target.h"
+
+using namespace std;
+using namespace ::testing;
+
+namespace extractor {
+namespace features {
+namespace {
+
+class MaxLexSourceGivenTargetTest : public Test {
+ protected:
+  virtual void SetUp() {
+    vector<string> source_words = {"f1", "f2", "f3"};
+    vector<string> target_words = {"e1", "e2", "e3"};
+
+    vocabulary = make_shared<MockVocabulary>();
+    for (size_t i = 0; i < source_words.size(); ++i) {
+      EXPECT_CALL(*vocabulary, GetTerminalValue(i))
+          .WillRepeatedly(Return(source_words[i]));
+    }
+    for (size_t i = 0; i < target_words.size(); ++i) {
+      EXPECT_CALL(*vocabulary, GetTerminalValue(i + source_words.size()))
+          .WillRepeatedly(Return(target_words[i]));
+    }
+
+    phrase_builder = make_shared<PhraseBuilder>(vocabulary);
+
+    table = make_shared<MockTranslationTable>();
+    for (size_t i = 0; i < source_words.size(); ++i) {
+      for (size_t j = 0; j < target_words.size(); ++j) {
+        int value = i - j;
+        EXPECT_CALL(*table, GetSourceGivenTargetScore(
+            source_words[i], target_words[j])).WillRepeatedly(Return(value));
+      }
+    }
+
+    for (size_t i = 0; i < source_words.size(); ++i) {
+      int value = i * 3;
+      EXPECT_CALL(*table, GetSourceGivenTargetScore(
+          source_words[i], DataArray::NULL_WORD_STR))
+          .WillRepeatedly(Return(value));
+    }
+
+    feature = make_shared<MaxLexSourceGivenTarget>(table);
+  }
+
+  shared_ptr<MockVocabulary> vocabulary;
+  shared_ptr<PhraseBuilder> phrase_builder;
+  shared_ptr<MockTranslationTable> table;
+  shared_ptr<MaxLexSourceGivenTarget> feature;
+};
+
+TEST_F(MaxLexSourceGivenTargetTest, TestGetName) {
+  EXPECT_EQ("MaxLexFgivenE", feature->GetName());
+}
+
+TEST_F(MaxLexSourceGivenTargetTest, TestScore) {
+  vector<int> source_symbols = {0, 1, 2};
+  Phrase source_phrase = phrase_builder->Build(source_symbols);
+  vector<int> target_symbols = {3, 4, 5};
+  Phrase target_phrase = phrase_builder->Build(target_symbols);
+  FeatureContext context(source_phrase, target_phrase, 0.3, 7, 11);
+  EXPECT_EQ(99 - log10(18), feature->Score(context));
+}
+
+} // namespace
+} // namespace features
+} // namespace extractor
diff --git a/extractor/features/max_lex_target_given_source.cc b/extractor/features/max_lex_target_given_source.cc
new file mode 100644
index 00000000..33783054
--- /dev/null
+++ b/extractor/features/max_lex_target_given_source.cc
@@ -0,0 +1,37 @@
+#include "max_lex_target_given_source.h"
+
+#include <cmath>
+
+#include "data_array.h"
+#include "translation_table.h"
+
+namespace extractor {
+namespace features {
+
+MaxLexTargetGivenSource::MaxLexTargetGivenSource(
+    shared_ptr<TranslationTable> table) :
+    table(table) {}
+
+double MaxLexTargetGivenSource::Score(const FeatureContext& context) const {
+  vector<string> source_words = context.source_phrase.GetWords();
+  source_words.push_back(DataArray::NULL_WORD_STR);
+  vector<string> target_words = context.target_phrase.GetWords();
+
+  double score = 0;
+  for (string target_word: target_words) {
+    double max_score = 0;
+    for (string source_word: source_words) {
+      max_score = max(max_score,
+          table->GetTargetGivenSourceScore(source_word, target_word));
+    }
+    score += max_score > 0 ? -log10(max_score) : MAX_SCORE;
+  }
+  return score;
+}
+
+string MaxLexTargetGivenSource::GetName() const {
+  return "MaxLexEgivenF";
+}
+
+} // namespace features
+} // namespace extractor
diff --git a/extractor/features/max_lex_target_given_source.h b/extractor/features/max_lex_target_given_source.h
new file mode 100644
index 00000000..c3c87327
--- /dev/null
+++ b/extractor/features/max_lex_target_given_source.h
@@ -0,0 +1,34 @@
+#ifndef _MAX_LEX_TARGET_GIVEN_SOURCE_H_
+#define _MAX_LEX_TARGET_GIVEN_SOURCE_H_
+
+#include <memory>
+
+#include "feature.h"
+
+using namespace std;
+
+namespace extractor {
+
+class TranslationTable;
+
+namespace features {
+
+/**
+ * Feature computing max(p(e | f)) across all pairs of words in the phrase pair.
+ */
+class MaxLexTargetGivenSource : public Feature {
+ public:
+  MaxLexTargetGivenSource(shared_ptr<TranslationTable> table);
+
+  double Score(const FeatureContext& context) const;
+
+  string GetName() const;
+
+ private:
+  shared_ptr<TranslationTable> table;
+};
+
+} // namespace features
+} // namespace extractor
+
+#endif
diff --git a/extractor/features/max_lex_target_given_source_test.cc b/extractor/features/max_lex_target_given_source_test.cc
new file mode 100644
index 00000000..6d0efd9c
--- /dev/null
+++ b/extractor/features/max_lex_target_given_source_test.cc
@@ -0,0 +1,78 @@
+#include <gtest/gtest.h>
+
+#include <cmath>
+#include <memory>
+#include <string>
+
+#include "data_array.h"
+#include "mocks/mock_translation_table.h"
+#include "mocks/mock_vocabulary.h"
+#include "phrase_builder.h"
+#include "max_lex_target_given_source.h"
+
+using namespace std;
+using namespace ::testing;
+
+namespace extractor {
+namespace features {
+namespace {
+
+class MaxLexTargetGivenSourceTest : public Test {
+ protected:
+  virtual void SetUp() {
+    vector<string> source_words = {"f1", "f2", "f3"};
+    vector<string> target_words = {"e1", "e2", "e3"};
+
+    vocabulary = make_shared<MockVocabulary>();
+    for (size_t i = 0; i < source_words.size(); ++i) {
+      EXPECT_CALL(*vocabulary, GetTerminalValue(i))
+          .WillRepeatedly(Return(source_words[i]));
+    }
+    for (size_t i = 0; i < target_words.size(); ++i) {
+      EXPECT_CALL(*vocabulary, GetTerminalValue(i + source_words.size()))
+          .WillRepeatedly(Return(target_words[i]));
+    }
+
+    phrase_builder = make_shared<PhraseBuilder>(vocabulary);
+
+    table = make_shared<MockTranslationTable>();
+    for (size_t i = 0; i < source_words.size(); ++i) {
+      for (size_t j = 0; j < target_words.size(); ++j) {
+        int value = i - j;
+        EXPECT_CALL(*table, GetTargetGivenSourceScore(
+            source_words[i], target_words[j])).WillRepeatedly(Return(value));
+      }
+    }
+
+    for (size_t i = 0; i < target_words.size(); ++i) {
+      int value = i * 3;
+      EXPECT_CALL(*table, GetTargetGivenSourceScore(
+          DataArray::NULL_WORD_STR, target_words[i]))
+          .WillRepeatedly(Return(value));
+    }
+
+    feature = make_shared<MaxLexTargetGivenSource>(table);
+  }
+
+  shared_ptr<MockVocabulary> vocabulary;
+  shared_ptr<PhraseBuilder> phrase_builder;
+  shared_ptr<MockTranslationTable> table;
+  shared_ptr<MaxLexTargetGivenSource> feature;
+};
+
+TEST_F(MaxLexTargetGivenSourceTest, TestGetName) {
+  EXPECT_EQ("MaxLexEgivenF", feature->GetName());
+}
+
+TEST_F(MaxLexTargetGivenSourceTest, TestScore) {
+  vector<int> source_symbols = {0, 1, 2};
+  Phrase source_phrase = phrase_builder->Build(source_symbols);
+  vector<int> target_symbols = {3, 4, 5};
+  Phrase target_phrase = phrase_builder->Build(target_symbols);
+  FeatureContext context(source_phrase, target_phrase, 0.3, 7, 19);
+  EXPECT_EQ(-log10(36), feature->Score(context));
+}
+
+} // namespace
+} // namespace features
+} // namespace extractor
diff --git a/extractor/features/sample_source_count.cc b/extractor/features/sample_source_count.cc
new file mode 100644
index 00000000..b110fc51
--- /dev/null
+++ b/extractor/features/sample_source_count.cc
@@ -0,0 +1,17 @@
+#include "sample_source_count.h"
+
+#include <cmath>
+
+namespace extractor {
+namespace features {
+
+double SampleSourceCount::Score(const FeatureContext& context) const {
+  return log10(1 + context.num_samples);
+}
+
+string SampleSourceCount::GetName() const {
+  return "SampleCountF";
+}
+
+} // namespace features
+} // namespace extractor
diff --git a/extractor/features/sample_source_count.h b/extractor/features/sample_source_count.h
new file mode 100644
index 00000000..ee6e59a0
--- /dev/null
+++ b/extractor/features/sample_source_count.h
@@ -0,0 +1,23 @@
+#ifndef _SAMPLE_SOURCE_COUNT_H_
+#define _SAMPLE_SOURCE_COUNT_H_
+
+#include "feature.h"
+
+namespace extractor {
+namespace features {
+
+/**
+ * Feature scoring the number of times the source phrase occurs in the sampled
+ * set.
+ */
+class SampleSourceCount : public Feature {
+ public:
+  double Score(const FeatureContext& context) const;
+
+  string GetName() const;
+};
+
+} // namespace features
+} // namespace extractor
+
+#endif
diff --git a/extractor/features/sample_source_count_test.cc b/extractor/features/sample_source_count_test.cc
new file mode 100644
index 00000000..63856b9d
--- /dev/null
+++ b/extractor/features/sample_source_count_test.cc
@@ -0,0 +1,40 @@
+#include <gtest/gtest.h>
+
+#include <cmath>
+#include <memory>
+#include <string>
+
+#include "sample_source_count.h"
+
+using namespace std;
+using namespace ::testing;
+
+namespace extractor {
+namespace features {
+namespace {
+
+class SampleSourceCountTest : public Test {
+ protected:
+  virtual void SetUp() {
+    feature = make_shared<SampleSourceCount>();
+  }
+
+  shared_ptr<SampleSourceCount> feature;
+};
+
+TEST_F(SampleSourceCountTest, TestGetName) {
+  EXPECT_EQ("SampleCountF", feature->GetName());
+}
+
+TEST_F(SampleSourceCountTest, TestScore) {
+  Phrase phrase;
+  FeatureContext context(phrase, phrase, 0, 3, 1);
+  EXPECT_EQ(log10(2), feature->Score(context));
+
+  context = FeatureContext(phrase, phrase, 3.2, 3, 9);
+  EXPECT_EQ(1.0, feature->Score(context));
+}
+
+} // namespace
+} // namespace features
+} // namespace extractor
diff --git a/extractor/features/target_given_source_coherent.cc b/extractor/features/target_given_source_coherent.cc
new file mode 100644
index 00000000..c4551d88
--- /dev/null
+++ b/extractor/features/target_given_source_coherent.cc
@@ -0,0 +1,18 @@
+#include "target_given_source_coherent.h"
+
+#include <cmath>
+
+namespace extractor {
+namespace features {
+
+double TargetGivenSourceCoherent::Score(const FeatureContext& context) const {
+  double prob = (double) context.pair_count / context.num_samples;
+  return prob > 0 ? -log10(prob) : MAX_SCORE;
+}
+
+string TargetGivenSourceCoherent::GetName() const {
+  return "EgivenFCoherent";
+}
+
+} // namespace features
+} // namespace extractor
diff --git a/extractor/features/target_given_source_coherent.h b/extractor/features/target_given_source_coherent.h
new file mode 100644
index 00000000..e66d70a5
--- /dev/null
+++ b/extractor/features/target_given_source_coherent.h
@@ -0,0 +1,23 @@
+#ifndef _TARGET_GIVEN_SOURCE_COHERENT_H_
+#define _TARGET_GIVEN_SOURCE_COHERENT_H_
+
+#include "feature.h"
+
+namespace extractor {
+namespace features {
+
+/**
+ * Feature computing the ratio of the phrase pair count over all source phrase
+ * occurrences (sampled).
+ */
+class TargetGivenSourceCoherent : public Feature {
+ public:
+  double Score(const FeatureContext& context) const;
+
+  string GetName() const;
+};
+
+} // namespace features
+} // namespace extractor
+
+#endif
diff --git a/extractor/features/target_given_source_coherent_test.cc b/extractor/features/target_given_source_coherent_test.cc
new file mode 100644
index 00000000..454105e1
--- /dev/null
+++ b/extractor/features/target_given_source_coherent_test.cc
@@ -0,0 +1,39 @@
+#include <gtest/gtest.h>
+
+#include <memory>
+#include <string>
+
+#include "target_given_source_coherent.h"
+
+using namespace std;
+using namespace ::testing;
+
+namespace extractor {
+namespace features {
+namespace {
+
+class TargetGivenSourceCoherentTest : public Test {
+ protected:
+  virtual void SetUp() {
+    feature = make_shared<TargetGivenSourceCoherent>();
+  }
+
+  shared_ptr<TargetGivenSourceCoherent> feature;
+};
+
+TEST_F(TargetGivenSourceCoherentTest, TestGetName) {
+  EXPECT_EQ("EgivenFCoherent", feature->GetName());
+}
+
+TEST_F(TargetGivenSourceCoherentTest, TestScore) {
+  Phrase phrase;
+  FeatureContext context(phrase, phrase, 0.3, 2, 20);
+  EXPECT_EQ(1.0, feature->Score(context));
+
+  context = FeatureContext(phrase, phrase, 1.9, 0, 1);
+  EXPECT_EQ(99.0, feature->Score(context));
+}
+
+} // namespace
+} // namespace features
+} // namespace extractor
diff --git a/extractor/grammar.cc b/extractor/grammar.cc
new file mode 100644
index 00000000..b45a8261
--- /dev/null
+++ b/extractor/grammar.cc
@@ -0,0 +1,43 @@
+#include "grammar.h"
+
+#include <iomanip>
+
+#include "rule.h"
+
+using namespace std;
+
+namespace extractor {
+
+Grammar::Grammar(const vector<Rule>& rules,
+                 const vector<string>& feature_names) :
+  rules(rules), feature_names(feature_names) {}
+
+vector<Rule> Grammar::GetRules() const {
+  return rules;
+}
+
+vector<string> Grammar::GetFeatureNames() const {
+  return feature_names;
+}
+
+ostream& operator<<(ostream& os, const Grammar& grammar) {
+  vector<Rule> rules = grammar.GetRules();
+  vector<string> feature_names = grammar.GetFeatureNames();
+  os << setprecision(12);
+  for (Rule rule: rules) {
+    os << "[X] ||| " << rule.source_phrase << " ||| "
+                     << rule.target_phrase << " |||";
+    for (size_t i = 0; i < rule.scores.size(); ++i) {
+      os << " " << feature_names[i] << "=" << rule.scores[i];
+    }
+    os << " |||";
+    for (auto link: rule.alignment) {
+      os << " " << link.first << "-" << link.second;
+    }
+    os << '\n';
+  }
+
+  return os;
+}
+
+} // namespace extractor
diff --git a/extractor/grammar.h b/extractor/grammar.h
new file mode 100644
index 00000000..fed41b16
--- /dev/null
+++ b/extractor/grammar.h
@@ -0,0 +1,34 @@
+#ifndef _GRAMMAR_H_
+#define _GRAMMAR_H_
+
+#include <iostream>
+#include <string>
+#include <vector>
+
+using namespace std;
+
+namespace extractor {
+
+class Rule;
+
+/**
+ * Grammar class wrapping the set of rules to be extracted.
+ */
+class Grammar {
+ public:
+  Grammar(const vector<Rule>& rules, const vector<string>& feature_names);
+
+  vector<Rule> GetRules() const;
+
+  vector<string> GetFeatureNames() const;
+
+  friend ostream& operator<<(ostream& os, const Grammar& grammar);
+
+ private:
+  vector<Rule> rules;
+  vector<string> feature_names;
+};
+
+} // namespace extractor
+
+#endif
diff --git a/extractor/grammar_extractor.cc b/extractor/grammar_extractor.cc
new file mode 100644
index 00000000..8050ce7b
--- /dev/null
+++ b/extractor/grammar_extractor.cc
@@ -0,0 +1,62 @@
+#include "grammar_extractor.h"
+
+#include <iterator>
+#include <sstream>
+#include <vector>
+
+#include "grammar.h"
+#include "rule.h"
+#include "rule_factory.h"
+#include "vocabulary.h"
+
+using namespace std;
+
+namespace extractor {
+
+GrammarExtractor::GrammarExtractor(
+    shared_ptr<SuffixArray> source_suffix_array,
+    shared_ptr<DataArray> target_data_array,
+    shared_ptr<Alignment> alignment, shared_ptr<Precomputation> precomputation,
+    shared_ptr<Scorer> scorer, int min_gap_size, int max_rule_span,
+    int max_nonterminals, int max_rule_symbols, int max_samples,
+    bool require_tight_phrases) :
+    vocabulary(make_shared<Vocabulary>()),
+    rule_factory(make_shared<HieroCachingRuleFactory>(
+        source_suffix_array, target_data_array, alignment, vocabulary,
+        precomputation, scorer, min_gap_size, max_rule_span, max_nonterminals,
+        max_rule_symbols, max_samples, require_tight_phrases)) {}
+
+GrammarExtractor::GrammarExtractor(
+    shared_ptr<Vocabulary> vocabulary,
+    shared_ptr<HieroCachingRuleFactory> rule_factory) :
+    vocabulary(vocabulary),
+    rule_factory(rule_factory) {}
+
+Grammar GrammarExtractor::GetGrammar(const string& sentence) {
+  vector<string> words = TokenizeSentence(sentence);
+  vector<int> word_ids = AnnotateWords(words);
+  return rule_factory->GetGrammar(word_ids);
+}
+
+vector<string> GrammarExtractor::TokenizeSentence(const string& sentence) {
+  vector<string> result;
+  result.push_back("<s>");
+
+  istringstream buffer(sentence);
+  copy(istream_iterator<string>(buffer),
+       istream_iterator<string>(),
+       back_inserter(result));
+
+  result.push_back("</s>");
+  return result;
+}
+
+vector<int> GrammarExtractor::AnnotateWords(const vector<string>& words) {
+  vector<int> result;
+  for (string word: words) {
+    result.push_back(vocabulary->GetTerminalIndex(word));
+  }
+  return result;
+}
+
+} // namespace extractor
diff --git a/extractor/grammar_extractor.h b/extractor/grammar_extractor.h
new file mode 100644
index 00000000..b36ceeb9
--- /dev/null
+++ b/extractor/grammar_extractor.h
@@ -0,0 +1,62 @@
+#ifndef _GRAMMAR_EXTRACTOR_H_
+#define _GRAMMAR_EXTRACTOR_H_
+
+#include <memory>
+#include <string>
+#include <vector>
+
+using namespace std;
+
+namespace extractor {
+
+class Alignment;
+class DataArray;
+class Grammar;
+class HieroCachingRuleFactory;
+class Precomputation;
+class Rule;
+class Scorer;
+class SuffixArray;
+class Vocabulary;
+
+/**
+ * Class wrapping all the logic for extracting the synchronous context free
+ * grammars.
+ */
+class GrammarExtractor {
+ public:
+  GrammarExtractor(
+      shared_ptr<SuffixArray> source_suffix_array,
+      shared_ptr<DataArray> target_data_array,
+      shared_ptr<Alignment> alignment,
+      shared_ptr<Precomputation> precomputation,
+      shared_ptr<Scorer> scorer,
+      int min_gap_size,
+      int max_rule_span,
+      int max_nonterminals,
+      int max_rule_symbols,
+      int max_samples,
+      bool require_tight_phrases);
+
+  // For testing only.
+  GrammarExtractor(shared_ptr<Vocabulary> vocabulary,
+                   shared_ptr<HieroCachingRuleFactory> rule_factory);
+
+  // Converts the sentence to a vector of word ids and uses the RuleFactory to
+  // extract the SCFG rules which may be used to decode the sentence.
+  Grammar GetGrammar(const string& sentence);
+
+ private:
+  // Splits the sentence in a vector of words.
+  vector<string> TokenizeSentence(const string& sentence);
+
+  // Maps the words to word ids.
+  vector<int> AnnotateWords(const vector<string>& words);
+
+  shared_ptr<Vocabulary> vocabulary;
+  shared_ptr<HieroCachingRuleFactory> rule_factory;
+};
+
+} // namespace extractor
+
+#endif
diff --git a/extractor/grammar_extractor_test.cc b/extractor/grammar_extractor_test.cc
new file mode 100644
index 00000000..823bb8b4
--- /dev/null
+++ b/extractor/grammar_extractor_test.cc
@@ -0,0 +1,51 @@
+#include <gtest/gtest.h>
+
+#include <memory>
+#include <string>
+#include <vector>
+
+#include "grammar.h"
+#include "grammar_extractor.h"
+#include "mocks/mock_rule_factory.h"
+#include "mocks/mock_vocabulary.h"
+#include "rule.h"
+
+using namespace std;
+using namespace ::testing;
+
+namespace extractor {
+namespace {
+
+TEST(GrammarExtractorTest, TestAnnotatingWords) {
+  shared_ptr<MockVocabulary> vocabulary = make_shared<MockVocabulary>();
+  EXPECT_CALL(*vocabulary, GetTerminalIndex("<s>"))
+      .WillRepeatedly(Return(0));
+  EXPECT_CALL(*vocabulary, GetTerminalIndex("Anna"))
+      .WillRepeatedly(Return(1));
+  EXPECT_CALL(*vocabulary, GetTerminalIndex("has"))
+      .WillRepeatedly(Return(2));
+  EXPECT_CALL(*vocabulary, GetTerminalIndex("many"))
+      .WillRepeatedly(Return(3));
+  EXPECT_CALL(*vocabulary, GetTerminalIndex("apples"))
+      .WillRepeatedly(Return(4));
+  EXPECT_CALL(*vocabulary, GetTerminalIndex("."))
+      .WillRepeatedly(Return(5));
+  EXPECT_CALL(*vocabulary, GetTerminalIndex("</s>"))
+      .WillRepeatedly(Return(6));
+
+  shared_ptr<MockHieroCachingRuleFactory> factory =
+      make_shared<MockHieroCachingRuleFactory>();
+  vector<int> word_ids = {0, 1, 2, 3, 3, 4, 5, 6};
+  vector<Rule> rules;
+  vector<string> feature_names;
+  Grammar grammar(rules, feature_names);
+  EXPECT_CALL(*factory, GetGrammar(word_ids))
+      .WillOnce(Return(grammar));
+
+  GrammarExtractor extractor(vocabulary, factory);
+  string sentence = "Anna has many many apples .";
+  extractor.GetGrammar(sentence);
+}
+
+} // namespace
+} // namespace extractor
diff --git a/extractor/matchings_finder.cc b/extractor/matchings_finder.cc
new file mode 100644
index 00000000..ceed6891
--- /dev/null
+++ b/extractor/matchings_finder.cc
@@ -0,0 +1,25 @@
+#include "matchings_finder.h"
+
+#include "suffix_array.h"
+#include "phrase_location.h"
+
+namespace extractor {
+
+MatchingsFinder::MatchingsFinder(shared_ptr<SuffixArray> suffix_array) :
+    suffix_array(suffix_array) {}
+
+MatchingsFinder::MatchingsFinder() {}
+
+MatchingsFinder::~MatchingsFinder() {}
+
+PhraseLocation MatchingsFinder::Find(PhraseLocation& location,
+                                     const string& word, int offset) {
+  if (location.sa_low == -1 && location.sa_high == -1) {
+    location.sa_low = 0;
+    location.sa_high = suffix_array->GetSize();
+  }
+
+  return suffix_array->Lookup(location.sa_low, location.sa_high, word, offset);
+}
+
+} // namespace extractor
diff --git a/extractor/matchings_finder.h b/extractor/matchings_finder.h
new file mode 100644
index 00000000..451f4a4c
--- /dev/null
+++ b/extractor/matchings_finder.h
@@ -0,0 +1,37 @@
+#ifndef _MATCHINGS_FINDER_H_
+#define _MATCHINGS_FINDER_H_
+
+#include <memory>
+#include <string>
+
+using namespace std;
+
+namespace extractor {
+
+class PhraseLocation;
+class SuffixArray;
+
+/**
+ * Class wrapping the suffix array lookup for a contiguous phrase.
+ */
+class MatchingsFinder {
+ public:
+  MatchingsFinder(shared_ptr<SuffixArray> suffix_array);
+
+  virtual ~MatchingsFinder();
+
+  // Uses the suffix array to search only for the last word of the phrase
+  // starting from the range in which the prefix of the phrase occurs.
+  virtual PhraseLocation Find(PhraseLocation& location, const string& word,
+                              int offset);
+
+ protected:
+  MatchingsFinder();
+
+ private:
+  shared_ptr<SuffixArray> suffix_array;
+};
+
+} // namespace extractor
+
+#endif
diff --git a/extractor/matchings_finder_test.cc b/extractor/matchings_finder_test.cc
new file mode 100644
index 00000000..d40e5191
--- /dev/null
+++ b/extractor/matchings_finder_test.cc
@@ -0,0 +1,44 @@
+#include <gtest/gtest.h>
+
+#include <memory>
+
+#include "matchings_finder.h"
+#include "mocks/mock_suffix_array.h"
+#include "phrase_location.h"
+
+using namespace std;
+using namespace ::testing;
+
+namespace extractor {
+namespace {
+
+class MatchingsFinderTest : public Test {
+ protected:
+  virtual void SetUp() {
+    suffix_array = make_shared<MockSuffixArray>();
+    EXPECT_CALL(*suffix_array, Lookup(0, 10, _, _))
+        .Times(1)
+        .WillOnce(Return(PhraseLocation(3, 5)));
+
+    matchings_finder = make_shared<MatchingsFinder>(suffix_array);
+  }
+
+  shared_ptr<MatchingsFinder> matchings_finder;
+  shared_ptr<MockSuffixArray> suffix_array;
+};
+
+TEST_F(MatchingsFinderTest, TestFind) {
+  PhraseLocation phrase_location(0, 10), expected_result(3, 5);
+  EXPECT_EQ(expected_result, matchings_finder->Find(phrase_location, "bla", 2));
+}
+
+TEST_F(MatchingsFinderTest, ResizeUnsetRange) {
+  EXPECT_CALL(*suffix_array, GetSize()).Times(1).WillOnce(Return(10));
+
+  PhraseLocation phrase_location, expected_result(3, 5);
+  EXPECT_EQ(expected_result, matchings_finder->Find(phrase_location, "bla", 2));
+  EXPECT_EQ(PhraseLocation(0, 10), phrase_location);
+}
+
+} // namespace
+} // namespace extractor
diff --git a/extractor/matchings_trie.cc b/extractor/matchings_trie.cc
new file mode 100644
index 00000000..7fb7a529
--- /dev/null
+++ b/extractor/matchings_trie.cc
@@ -0,0 +1,29 @@
+#include "matchings_trie.h"
+
+namespace extractor {
+
+MatchingsTrie::MatchingsTrie() {
+  root = make_shared<TrieNode>();
+}
+
+MatchingsTrie::~MatchingsTrie() {
+  DeleteTree(root);
+}
+
+shared_ptr<TrieNode> MatchingsTrie::GetRoot() const {
+  return root;
+}
+
+void MatchingsTrie::DeleteTree(shared_ptr<TrieNode> root) {
+  if (root != NULL) {
+    for (auto child: root->children) {
+      DeleteTree(child.second);
+    }
+    if (root->suffix_link != NULL) {
+      root->suffix_link.reset();
+    }
+    root.reset();
+  }
+}
+
+} // namespace extractor
diff --git a/extractor/matchings_trie.h b/extractor/matchings_trie.h
new file mode 100644
index 00000000..1fb29693
--- /dev/null
+++ b/extractor/matchings_trie.h
@@ -0,0 +1,66 @@
+#ifndef _MATCHINGS_TRIE_
+#define _MATCHINGS_TRIE_
+
+#include <memory>
+#include <unordered_map>
+
+#include "phrase.h"
+#include "phrase_location.h"
+
+using namespace std;
+
+namespace extractor {
+
+/**
+ * Trie node containing all the occurrences of the corresponding phrase in the
+ * source data.
+ */
+struct TrieNode {
+  TrieNode(shared_ptr<TrieNode> suffix_link = shared_ptr<TrieNode>(),
+           Phrase phrase = Phrase(),
+           PhraseLocation matchings = PhraseLocation()) :
+      suffix_link(suffix_link), phrase(phrase), matchings(matchings) {}
+
+  // Adds a trie node as a child of the current node.
+  void AddChild(int key, shared_ptr<TrieNode> child_node) {
+    children[key] = child_node;
+  }
+
+  // Checks if a child exists for a given key.
+  bool HasChild(int key) {
+    return children.count(key);
+  }
+
+  // Gets the child corresponding to the given key.
+  shared_ptr<TrieNode> GetChild(int key) {
+    return children[key];
+  }
+
+  shared_ptr<TrieNode> suffix_link;
+  Phrase phrase;
+  PhraseLocation matchings;
+  unordered_map<int, shared_ptr<TrieNode> > children;
+};
+
+/**
+ * Trie containing all the phrases that can be obtained from a sentence.
+ */
+class MatchingsTrie {
+ public:
+  MatchingsTrie();
+
+  virtual ~MatchingsTrie();
+
+  // Returns the root of the trie.
+  shared_ptr<TrieNode> GetRoot() const;
+
+ private:
+  // Recursively deletes a subtree of the trie.
+  void DeleteTree(shared_ptr<TrieNode> root);
+
+  shared_ptr<TrieNode> root;
+};
+
+} // namespace extractor
+
+#endif
diff --git a/extractor/mocks/mock_alignment.h b/extractor/mocks/mock_alignment.h
new file mode 100644
index 00000000..299c3d1c
--- /dev/null
+++ b/extractor/mocks/mock_alignment.h
@@ -0,0 +1,14 @@
+#include <gmock/gmock.h>
+
+#include "alignment.h"
+
+namespace extractor {
+
+typedef vector<pair<int, int> > SentenceLinks;
+
+class MockAlignment : public Alignment {
+ public:
+  MOCK_CONST_METHOD1(GetLinks, SentenceLinks(int sentence_id));
+};
+
+} // namespace extractor
diff --git a/extractor/mocks/mock_data_array.h b/extractor/mocks/mock_data_array.h
new file mode 100644
index 00000000..6f85abb4
--- /dev/null
+++ b/extractor/mocks/mock_data_array.h
@@ -0,0 +1,23 @@
+#include <gmock/gmock.h>
+
+#include "data_array.h"
+
+namespace extractor {
+
+class MockDataArray : public DataArray {
+ public:
+  MOCK_CONST_METHOD0(GetData, const vector<int>&());
+  MOCK_CONST_METHOD1(AtIndex, int(int index));
+  MOCK_CONST_METHOD1(GetWordAtIndex, string(int index));
+  MOCK_CONST_METHOD0(GetSize, int());
+  MOCK_CONST_METHOD0(GetVocabularySize, int());
+  MOCK_CONST_METHOD1(HasWord, bool(const string& word));
+  MOCK_CONST_METHOD1(GetWordId, int(const string& word));
+  MOCK_CONST_METHOD1(GetWord, string(int word_id));
+  MOCK_CONST_METHOD1(GetSentenceLength, int(int sentence_id));
+  MOCK_CONST_METHOD0(GetNumSentences, int());
+  MOCK_CONST_METHOD1(GetSentenceStart, int(int sentence_id));
+  MOCK_CONST_METHOD1(GetSentenceId, int(int position));
+};
+
+} // namespace extractor
diff --git a/extractor/mocks/mock_fast_intersector.h b/extractor/mocks/mock_fast_intersector.h
new file mode 100644
index 00000000..f0b628d7
--- /dev/null
+++ b/extractor/mocks/mock_fast_intersector.h
@@ -0,0 +1,15 @@
+#include <gmock/gmock.h>
+
+#include "fast_intersector.h"
+#include "phrase.h"
+#include "phrase_location.h"
+
+namespace extractor {
+
+class MockFastIntersector : public FastIntersector {
+ public:
+  MOCK_METHOD3(Intersect, PhraseLocation(PhraseLocation&, PhraseLocation&,
+                                         const Phrase&));
+};
+
+} // namespace extractor
diff --git a/extractor/mocks/mock_feature.h b/extractor/mocks/mock_feature.h
new file mode 100644
index 00000000..0b0f0ead
--- /dev/null
+++ b/extractor/mocks/mock_feature.h
@@ -0,0 +1,15 @@
+#include <gmock/gmock.h>
+
+#include "features/feature.h"
+
+namespace extractor {
+namespace features {
+
+class MockFeature : public Feature {
+ public:
+  MOCK_CONST_METHOD1(Score, double(const FeatureContext& context));
+  MOCK_CONST_METHOD0(GetName, string());
+};
+
+} // namespace features
+} // namespace extractor
diff --git a/extractor/mocks/mock_matchings_finder.h b/extractor/mocks/mock_matchings_finder.h
new file mode 100644
index 00000000..827526fd
--- /dev/null
+++ b/extractor/mocks/mock_matchings_finder.h
@@ -0,0 +1,13 @@
+#include <gmock/gmock.h>
+
+#include "matchings_finder.h"
+#include "phrase_location.h"
+
+namespace extractor {
+
+class MockMatchingsFinder : public MatchingsFinder {
+ public:
+  MOCK_METHOD3(Find, PhraseLocation(PhraseLocation&, const string&, int));
+};
+
+} // namespace extractor
diff --git a/extractor/mocks/mock_precomputation.h b/extractor/mocks/mock_precomputation.h
new file mode 100644
index 00000000..8753343e
--- /dev/null
+++ b/extractor/mocks/mock_precomputation.h
@@ -0,0 +1,12 @@
+#include <gmock/gmock.h>
+
+#include "precomputation.h"
+
+namespace extractor {
+
+class MockPrecomputation : public Precomputation {
+ public:
+  MOCK_CONST_METHOD0(GetCollocations, const Index&());
+};
+
+} // namespace extractor
diff --git a/extractor/mocks/mock_rule_extractor.h b/extractor/mocks/mock_rule_extractor.h
new file mode 100644
index 00000000..aad11651
--- /dev/null
+++ b/extractor/mocks/mock_rule_extractor.h
@@ -0,0 +1,16 @@
+#include <gmock/gmock.h>
+
+#include "phrase.h"
+#include "phrase_builder.h"
+#include "rule.h"
+#include "rule_extractor.h"
+
+namespace extractor {
+
+class MockRuleExtractor : public RuleExtractor {
+ public:
+  MOCK_CONST_METHOD2(ExtractRules, vector<Rule>(const Phrase&,
+      const PhraseLocation&));
+};
+
+} // namespace extractor
diff --git a/extractor/mocks/mock_rule_extractor_helper.h b/extractor/mocks/mock_rule_extractor_helper.h
new file mode 100644
index 00000000..468468f6
--- /dev/null
+++ b/extractor/mocks/mock_rule_extractor_helper.h
@@ -0,0 +1,82 @@
+#include <gmock/gmock.h>
+
+#include <vector>
+
+#include "rule_extractor_helper.h"
+
+using namespace std;
+
+namespace extractor {
+
+typedef unordered_map<int, int> Indexes;
+
+class MockRuleExtractorHelper : public RuleExtractorHelper {
+ public:
+  MOCK_CONST_METHOD5(GetLinksSpans, void(vector<int>&, vector<int>&,
+      vector<int>&, vector<int>&, int));
+  MOCK_CONST_METHOD4(CheckAlignedTerminals, bool(const vector<int>&,
+      const vector<int>&, const vector<int>&, int));
+  MOCK_CONST_METHOD4(CheckTightPhrases, bool(const vector<int>&,
+      const vector<int>&, const vector<int>&, int));
+  MOCK_CONST_METHOD1(GetGapOrder, vector<int>(const vector<pair<int, int> >&));
+  MOCK_CONST_METHOD4(GetSourceIndexes, Indexes(const vector<int>&,
+      const vector<int>&, int, int));
+
+  // We need to implement these methods, because Google Mock doesn't support
+  // methods with more than 10 arguments.
+  bool FindFixPoint(
+      int, int, const vector<int>&, const vector<int>&, int& target_phrase_low,
+      int& target_phrase_high, const vector<int>&, const vector<int>&,
+      int& source_back_low, int& source_back_high, int, int, int, int, bool,
+      bool, bool) const {
+    target_phrase_low = this->target_phrase_low;
+    target_phrase_high = this->target_phrase_high;
+    source_back_low = this->source_back_low;
+    source_back_high = this->source_back_high;
+    return find_fix_point;
+  }
+
+  bool GetGaps(vector<pair<int, int> >& source_gaps,
+               vector<pair<int, int> >& target_gaps,
+               const vector<int>&, const vector<int>&, const vector<int>&,
+               const vector<int>&, const vector<int>&, const vector<int>&,
+               int, int, int, int, int, int, int& num_symbols,
+               bool& met_constraints) const {
+    source_gaps = this->source_gaps;
+    target_gaps = this->target_gaps;
+    num_symbols = this->num_symbols;
+    met_constraints = this->met_constraints;
+    return get_gaps;
+  }
+
+  void SetUp(
+      int target_phrase_low, int target_phrase_high, int source_back_low,
+      int source_back_high, bool find_fix_point,
+      vector<pair<int, int> > source_gaps, vector<pair<int, int> > target_gaps,
+      int num_symbols, bool met_constraints, bool get_gaps) {
+    this->target_phrase_low = target_phrase_low;
+    this->target_phrase_high = target_phrase_high;
+    this->source_back_low = source_back_low;
+    this->source_back_high = source_back_high;
+    this->find_fix_point = find_fix_point;
+    this->source_gaps = source_gaps;
+    this->target_gaps = target_gaps;
+    this->num_symbols = num_symbols;
+    this->met_constraints = met_constraints;
+    this->get_gaps = get_gaps;
+  }
+
+ private:
+  int target_phrase_low;
+  int target_phrase_high;
+  int source_back_low;
+  int source_back_high;
+  bool find_fix_point;
+  vector<pair<int, int> > source_gaps;
+  vector<pair<int, int> > target_gaps;
+  int num_symbols;
+  bool met_constraints;
+  bool get_gaps;
+};
+
+} // namespace extractor
diff --git a/extractor/mocks/mock_rule_factory.h b/extractor/mocks/mock_rule_factory.h
new file mode 100644
index 00000000..7389b396
--- /dev/null
+++ b/extractor/mocks/mock_rule_factory.h
@@ -0,0 +1,13 @@
+#include <gmock/gmock.h>
+
+#include "grammar.h"
+#include "rule_factory.h"
+
+namespace extractor {
+
+class MockHieroCachingRuleFactory : public HieroCachingRuleFactory {
+ public:
+  MOCK_METHOD1(GetGrammar, Grammar(const vector<int>& word_ids));
+};
+
+} // namespace extractor
diff --git a/extractor/mocks/mock_sampler.h b/extractor/mocks/mock_sampler.h
new file mode 100644
index 00000000..75c43c27
--- /dev/null
+++ b/extractor/mocks/mock_sampler.h
@@ -0,0 +1,13 @@
+#include <gmock/gmock.h>
+
+#include "phrase_location.h"
+#include "sampler.h"
+
+namespace extractor {
+
+class MockSampler : public Sampler {
+ public:
+  MOCK_CONST_METHOD1(Sample, PhraseLocation(const PhraseLocation& location));
+};
+
+} // namespace extractor
diff --git a/extractor/mocks/mock_scorer.h b/extractor/mocks/mock_scorer.h
new file mode 100644
index 00000000..cc0c444d
--- /dev/null
+++ b/extractor/mocks/mock_scorer.h
@@ -0,0 +1,15 @@
+#include <gmock/gmock.h>
+
+#include "scorer.h"
+#include "features/feature.h"
+
+namespace extractor {
+
+class MockScorer : public Scorer {
+ public:
+  MOCK_CONST_METHOD1(Score, vector<double>(
+      const features::FeatureContext& context));
+  MOCK_CONST_METHOD0(GetFeatureNames, vector<string>());
+};
+
+} // namespace extractor
diff --git a/extractor/mocks/mock_suffix_array.h b/extractor/mocks/mock_suffix_array.h
new file mode 100644
index 00000000..7018acc7
--- /dev/null
+++ b/extractor/mocks/mock_suffix_array.h
@@ -0,0 +1,23 @@
+#include <gmock/gmock.h>
+
+#include <memory>
+#include <string>
+
+#include "data_array.h"
+#include "phrase_location.h"
+#include "suffix_array.h"
+
+using namespace std;
+
+namespace extractor {
+
+class MockSuffixArray : public SuffixArray {
+ public:
+  MOCK_CONST_METHOD0(GetSize, int());
+  MOCK_CONST_METHOD0(GetData, shared_ptr<DataArray>());
+  MOCK_CONST_METHOD0(BuildLCPArray, vector<int>());
+  MOCK_CONST_METHOD1(GetSuffix, int(int));
+  MOCK_CONST_METHOD4(Lookup, PhraseLocation(int, int, const string& word, int));
+};
+
+} // namespace extractor
diff --git a/extractor/mocks/mock_target_phrase_extractor.h b/extractor/mocks/mock_target_phrase_extractor.h
new file mode 100644
index 00000000..6aad853c
--- /dev/null
+++ b/extractor/mocks/mock_target_phrase_extractor.h
@@ -0,0 +1,16 @@
+#include <gmock/gmock.h>
+
+#include "target_phrase_extractor.h"
+
+namespace extractor {
+
+typedef pair<Phrase, PhraseAlignment> PhraseExtract;
+
+class MockTargetPhraseExtractor : public TargetPhraseExtractor {
+ public:
+  MOCK_CONST_METHOD6(ExtractPhrases, vector<PhraseExtract>(
+      const vector<pair<int, int> > &, const vector<int>&, int, int,
+      const unordered_map<int, int>&, int));
+};
+
+} // namespace extractor
diff --git a/extractor/mocks/mock_translation_table.h b/extractor/mocks/mock_translation_table.h
new file mode 100644
index 00000000..307e4282
--- /dev/null
+++ b/extractor/mocks/mock_translation_table.h
@@ -0,0 +1,13 @@
+#include <gmock/gmock.h>
+
+#include "translation_table.h"
+
+namespace extractor {
+
+class MockTranslationTable : public TranslationTable {
+ public:
+  MOCK_METHOD2(GetSourceGivenTargetScore, double(const string&, const string&));
+  MOCK_METHOD2(GetTargetGivenSourceScore, double(const string&, const string&));
+};
+
+} // namespace extractor
diff --git a/extractor/mocks/mock_vocabulary.h b/extractor/mocks/mock_vocabulary.h
new file mode 100644
index 00000000..042c9ce2
--- /dev/null
+++ b/extractor/mocks/mock_vocabulary.h
@@ -0,0 +1,13 @@
+#include <gmock/gmock.h>
+
+#include "vocabulary.h"
+
+namespace extractor {
+
+class MockVocabulary : public Vocabulary {
+ public:
+  MOCK_METHOD1(GetTerminalValue, string(int word_id));
+  MOCK_METHOD1(GetTerminalIndex, int(const string& word));
+};
+
+} // namespace extractor
diff --git a/extractor/phrase.cc b/extractor/phrase.cc
new file mode 100644
index 00000000..e619bfe5
--- /dev/null
+++ b/extractor/phrase.cc
@@ -0,0 +1,58 @@
+#include "phrase.h"
+
+namespace extractor {
+
+int Phrase::Arity() const {
+  return var_pos.size();
+}
+
+int Phrase::GetChunkLen(int index) const {
+  if (var_pos.size() == 0) {
+    return symbols.size();
+  } else if (index == 0) {
+    return var_pos[0];
+  } else if (index == var_pos.size()) {
+    return symbols.size() - var_pos.back() - 1;
+  } else {
+    return var_pos[index] - var_pos[index - 1] - 1;
+  }
+}
+
+vector<int> Phrase::Get() const {
+  return symbols;
+}
+
+int Phrase::GetSymbol(int position) const {
+  return symbols[position];
+}
+
+int Phrase::GetNumSymbols() const {
+  return symbols.size();
+}
+
+vector<string> Phrase::GetWords() const {
+  return words;
+}
+
+bool Phrase::operator<(const Phrase& other) const {
+  return symbols < other.symbols;
+}
+
+ostream& operator<<(ostream& os, const Phrase& phrase) {
+  int current_word = 0;
+  for (size_t i = 0; i < phrase.symbols.size(); ++i) {
+    if (phrase.symbols[i] < 0) {
+      os << "[X," << -phrase.symbols[i] << "]";
+    } else {
+      os << phrase.words[current_word];
+      ++current_word;
+    }
+
+    if (i + 1 < phrase.symbols.size()) {
+      os << " ";
+    }
+  }
+  return os;
+}
+
+} // namspace extractor
diff --git a/extractor/phrase.h b/extractor/phrase.h
new file mode 100644
index 00000000..a8e91e3c
--- /dev/null
+++ b/extractor/phrase.h
@@ -0,0 +1,52 @@
+#ifndef _PHRASE_H_
+#define _PHRASE_H_
+
+#include <iostream>
+#include <string>
+#include <vector>
+
+#include "phrase_builder.h"
+
+using namespace std;
+
+namespace extractor {
+
+/**
+ * Structure containing the data for a phrase.
+ */
+class Phrase {
+ public:
+  friend Phrase PhraseBuilder::Build(const vector<int>& phrase);
+
+  // Returns the number of nonterminals in the phrase.
+  int Arity() const;
+
+  // Returns the number of terminals (length) for the given chunk. (A chunk is a
+  // contiguous sequence of terminals in the phrase).
+  int GetChunkLen(int index) const;
+
+  // Returns the symbols (word ids) marking up the phrase.
+  vector<int> Get() const;
+
+  // Returns the symbol located at the given position in the phrase.
+  int GetSymbol(int position) const;
+
+  // Returns the number of symbols in the phrase.
+  int GetNumSymbols() const;
+
+  // Returns the words making up the phrase. (Nonterminals are stripped out.)
+  vector<string> GetWords() const;
+
+  bool operator<(const Phrase& other) const;
+
+  friend ostream& operator<<(ostream& os, const Phrase& phrase);
+
+ private:
+  vector<int> symbols;
+  vector<int> var_pos;
+  vector<string> words;
+};
+
+} // namespace extractor
+
+#endif
diff --git a/extractor/phrase_builder.cc b/extractor/phrase_builder.cc
new file mode 100644
index 00000000..9faee4be
--- /dev/null
+++ b/extractor/phrase_builder.cc
@@ -0,0 +1,48 @@
+#include "phrase_builder.h"
+
+#include "phrase.h"
+#include "vocabulary.h"
+
+namespace extractor {
+
+PhraseBuilder::PhraseBuilder(shared_ptr<Vocabulary> vocabulary) :
+    vocabulary(vocabulary) {}
+
+Phrase PhraseBuilder::Build(const vector<int>& symbols) {
+  Phrase phrase;
+  phrase.symbols = symbols;
+  for (size_t i = 0; i < symbols.size(); ++i) {
+    if (vocabulary->IsTerminal(symbols[i])) {
+      phrase.words.push_back(vocabulary->GetTerminalValue(symbols[i]));
+    } else {
+      phrase.var_pos.push_back(i);
+    }
+  }
+  return phrase;
+}
+
+Phrase PhraseBuilder::Extend(const Phrase& phrase, bool start_x, bool end_x) {
+  vector<int> symbols = phrase.Get();
+  int num_nonterminals = 0;
+  if (start_x) {
+    num_nonterminals = 1;
+    symbols.insert(symbols.begin(),
+        vocabulary->GetNonterminalIndex(num_nonterminals));
+  }
+
+  for (size_t i = start_x; i < symbols.size(); ++i) {
+    if (!vocabulary->IsTerminal(symbols[i])) {
+      ++num_nonterminals;
+      symbols[i] = vocabulary->GetNonterminalIndex(num_nonterminals);
+    }
+  }
+
+  if (end_x) {
+    ++num_nonterminals;
+    symbols.push_back(vocabulary->GetNonterminalIndex(num_nonterminals));
+  }
+
+  return Build(symbols);
+}
+
+} // namespace extractor
diff --git a/extractor/phrase_builder.h b/extractor/phrase_builder.h
new file mode 100644
index 00000000..de86dbae
--- /dev/null
+++ b/extractor/phrase_builder.h
@@ -0,0 +1,33 @@
+#ifndef _PHRASE_BUILDER_H_
+#define _PHRASE_BUILDER_H_
+
+#include <memory>
+#include <vector>
+
+using namespace std;
+
+namespace extractor {
+
+class Phrase;
+class Vocabulary;
+
+/**
+ * Component for constructing phrases.
+ */
+class PhraseBuilder {
+ public:
+  PhraseBuilder(shared_ptr<Vocabulary> vocabulary);
+
+  // Constructs a phrase starting from an array of symbols.
+  Phrase Build(const vector<int>& symbols);
+
+  // Extends a phrase with a leading and/or trailing nonterminal.
+  Phrase Extend(const Phrase& phrase, bool start_x, bool end_x);
+
+ private:
+  shared_ptr<Vocabulary> vocabulary;
+};
+
+} // namespace extractor
+
+#endif
diff --git a/extractor/phrase_location.cc b/extractor/phrase_location.cc
new file mode 100644
index 00000000..678ae270
--- /dev/null
+++ b/extractor/phrase_location.cc
@@ -0,0 +1,43 @@
+#include "phrase_location.h"
+
+namespace extractor {
+
+PhraseLocation::PhraseLocation(int sa_low, int sa_high) :
+    sa_low(sa_low), sa_high(sa_high), num_subpatterns(0) {}
+
+PhraseLocation::PhraseLocation(const vector<int>& matchings,
+                               int num_subpatterns) :
+    sa_low(0), sa_high(0),
+    matchings(make_shared<vector<int> >(matchings)),
+    num_subpatterns(num_subpatterns) {}
+
+bool PhraseLocation::IsEmpty() const {
+  return GetSize() == 0;
+}
+
+int PhraseLocation::GetSize() const {
+  if (num_subpatterns > 0) {
+    return matchings->size();
+  } else {
+    return sa_high - sa_low;
+  }
+}
+
+bool operator==(const PhraseLocation& a, const PhraseLocation& b) {
+  if (a.sa_low != b.sa_low || a.sa_high != b.sa_high ||
+      a.num_subpatterns != b.num_subpatterns) {
+    return false;
+  }
+
+  if (a.matchings == NULL && b.matchings == NULL) {
+    return true;
+  }
+
+  if (a.matchings == NULL || b.matchings == NULL) {
+    return false;
+  }
+
+  return *a.matchings == *b.matchings;
+}
+
+} // namespace extractor
diff --git a/extractor/phrase_location.h b/extractor/phrase_location.h
new file mode 100644
index 00000000..91950e03
--- /dev/null
+++ b/extractor/phrase_location.h
@@ -0,0 +1,41 @@
+#ifndef _PHRASE_LOCATION_H_
+#define _PHRASE_LOCATION_H_
+
+#include <memory>
+#include <vector>
+
+using namespace std;
+
+namespace extractor {
+
+/**
+ * Structure containing information about the occurrences of a phrase in the
+ * source data.
+ *
+ * Every consecutive (disjoint) group of num_subpatterns entries in matchings
+ * vector encodes an occurrence of the phrase. The i-th entry of a group
+ * represents the start of the i-th subpattern of the phrase. If the phrase
+ * doesn't contain any nonterminals, then it may also be represented as the
+ * range in the suffix array which matches the phrase.
+ */
+struct PhraseLocation {
+  PhraseLocation(int sa_low = -1, int sa_high = -1);
+
+  PhraseLocation(const vector<int>& matchings, int num_subpatterns);
+
+  // Checks if a phrase has any occurrences in the source data.
+  bool IsEmpty() const;
+
+  // Returns the number of occurrences of a phrase in the source data.
+  int GetSize() const;
+
+  friend bool operator==(const PhraseLocation& a, const PhraseLocation& b);
+
+  int sa_low, sa_high;
+  shared_ptr<vector<int> > matchings;
+  int num_subpatterns;
+};
+
+} // namespace extractor
+
+#endif
diff --git a/extractor/phrase_test.cc b/extractor/phrase_test.cc
new file mode 100644
index 00000000..3ba9368a
--- /dev/null
+++ b/extractor/phrase_test.cc
@@ -0,0 +1,83 @@
+#include <gtest/gtest.h>
+
+#include <memory>
+#include <vector>
+
+#include "mocks/mock_vocabulary.h"
+#include "phrase.h"
+#include "phrase_builder.h"
+
+using namespace std;
+using namespace ::testing;
+
+namespace extractor {
+namespace {
+
+class PhraseTest : public Test {
+ protected:
+  virtual void SetUp() {
+    shared_ptr<MockVocabulary> vocabulary = make_shared<MockVocabulary>();
+    vector<string> words = {"w1", "w2", "w3", "w4"};
+    for (size_t i = 0; i < words.size(); ++i) {
+      EXPECT_CALL(*vocabulary, GetTerminalValue(i + 1))
+          .WillRepeatedly(Return(words[i]));
+    }
+    shared_ptr<PhraseBuilder> phrase_builder =
+        make_shared<PhraseBuilder>(vocabulary);
+
+    symbols1 = vector<int>{1, 2, 3};
+    phrase1 = phrase_builder->Build(symbols1);
+    symbols2 = vector<int>{1, 2, -1, 3, -2, 4};
+    phrase2 = phrase_builder->Build(symbols2);
+  }
+
+  vector<int> symbols1, symbols2;
+  Phrase phrase1, phrase2;
+};
+
+TEST_F(PhraseTest, TestArity) {
+  EXPECT_EQ(0, phrase1.Arity());
+  EXPECT_EQ(2, phrase2.Arity());
+}
+
+TEST_F(PhraseTest, GetChunkLen) {
+  EXPECT_EQ(3, phrase1.GetChunkLen(0));
+
+  EXPECT_EQ(2, phrase2.GetChunkLen(0));
+  EXPECT_EQ(1, phrase2.GetChunkLen(1));
+  EXPECT_EQ(1, phrase2.GetChunkLen(2));
+}
+
+TEST_F(PhraseTest, TestGet) {
+  EXPECT_EQ(symbols1, phrase1.Get());
+  EXPECT_EQ(symbols2, phrase2.Get());
+}
+
+TEST_F(PhraseTest, TestGetSymbol) {
+  for (size_t i = 0; i < symbols1.size(); ++i) {
+    EXPECT_EQ(symbols1[i], phrase1.GetSymbol(i));
+  }
+  for (size_t i = 0; i < symbols2.size(); ++i) {
+    EXPECT_EQ(symbols2[i], phrase2.GetSymbol(i));
+  }
+}
+
+TEST_F(PhraseTest, TestGetNumSymbols) {
+  EXPECT_EQ(3, phrase1.GetNumSymbols());
+  EXPECT_EQ(6, phrase2.GetNumSymbols());
+}
+
+TEST_F(PhraseTest, TestGetWords) {
+  vector<string> expected_words = {"w1", "w2", "w3"};
+  EXPECT_EQ(expected_words, phrase1.GetWords());
+  expected_words = {"w1", "w2", "w3", "w4"};
+  EXPECT_EQ(expected_words, phrase2.GetWords());
+}
+
+TEST_F(PhraseTest, TestComparator) {
+  EXPECT_FALSE(phrase1 < phrase2);
+  EXPECT_TRUE(phrase2 < phrase1);
+}
+
+} // namespace
+} // namespace extractor
diff --git a/extractor/precomputation.cc b/extractor/precomputation.cc
new file mode 100644
index 00000000..b3906943
--- /dev/null
+++ b/extractor/precomputation.cc
@@ -0,0 +1,189 @@
+#include "precomputation.h"
+
+#include <iostream>
+#include <queue>
+
+#include "data_array.h"
+#include "suffix_array.h"
+
+using namespace std;
+
+namespace extractor {
+
+int Precomputation::FIRST_NONTERMINAL = -1;
+int Precomputation::SECOND_NONTERMINAL = -2;
+
+Precomputation::Precomputation(
+    shared_ptr<SuffixArray> suffix_array, int num_frequent_patterns,
+    int num_super_frequent_patterns, int max_rule_span,
+    int max_rule_symbols, int min_gap_size,
+    int max_frequent_phrase_len, int min_frequency) {
+  vector<int> data = suffix_array->GetData()->GetData();
+  vector<vector<int> > frequent_patterns = FindMostFrequentPatterns(
+      suffix_array, data, num_frequent_patterns, max_frequent_phrase_len,
+      min_frequency);
+
+  // Construct sets containing the frequent and superfrequent contiguous
+  // collocations.
+  unordered_set<vector<int>, VectorHash> frequent_patterns_set;
+  unordered_set<vector<int>, VectorHash> super_frequent_patterns_set;
+  for (size_t i = 0; i < frequent_patterns.size(); ++i) {
+    frequent_patterns_set.insert(frequent_patterns[i]);
+    if (i < num_super_frequent_patterns) {
+      super_frequent_patterns_set.insert(frequent_patterns[i]);
+    }
+  }
+
+  vector<tuple<int, int, int> > matchings;
+  for (size_t i = 0; i < data.size(); ++i) {
+    // If the sentence is over, add all the discontiguous frequent patterns to
+    // the index.
+    if (data[i] == DataArray::END_OF_LINE) {
+      AddCollocations(matchings, data, max_rule_span, min_gap_size,
+          max_rule_symbols);
+      matchings.clear();
+      continue;
+    }
+    vector<int> pattern;
+    // Find all the contiguous frequent patterns starting at position i.
+    for (int j = 1; j <= max_frequent_phrase_len && i + j <= data.size(); ++j) {
+      pattern.push_back(data[i + j - 1]);
+      if (frequent_patterns_set.count(pattern)) {
+        int is_super_frequent = super_frequent_patterns_set.count(pattern);
+        matchings.push_back(make_tuple(i, j, is_super_frequent));
+      } else {
+        // If the current pattern is not frequent, any longer pattern having the
+        // current pattern as prefix will not be frequent.
+        break;
+      }
+    }
+  }
+}
+
+Precomputation::Precomputation() {}
+
+Precomputation::~Precomputation() {}
+
+vector<vector<int> > Precomputation::FindMostFrequentPatterns(
+    shared_ptr<SuffixArray> suffix_array, const vector<int>& data,
+    int num_frequent_patterns, int max_frequent_phrase_len, int min_frequency) {
+  vector<int> lcp = suffix_array->BuildLCPArray();
+  vector<int> run_start(max_frequent_phrase_len);
+
+  // Find all the patterns occurring at least min_frequency times.
+  priority_queue<pair<int, pair<int, int> > > heap;
+  for (size_t i = 1; i < lcp.size(); ++i) {
+    for (int len = lcp[i]; len < max_frequent_phrase_len; ++len) {
+      int frequency = i - run_start[len];
+      if (frequency >= min_frequency) {
+        heap.push(make_pair(frequency,
+            make_pair(suffix_array->GetSuffix(run_start[len]), len + 1)));
+      }
+      run_start[len] = i;
+    }
+  }
+
+  // Extract the most frequent patterns.
+  vector<vector<int> > frequent_patterns;
+  while (frequent_patterns.size() < num_frequent_patterns && !heap.empty()) {
+    int start = heap.top().second.first;
+    int len = heap.top().second.second;
+    heap.pop();
+
+    vector<int> pattern(data.begin() + start, data.begin() + start + len);
+    if (find(pattern.begin(), pattern.end(), DataArray::END_OF_LINE) ==
+        pattern.end()) {
+      frequent_patterns.push_back(pattern);
+    }
+  }
+  return frequent_patterns;
+}
+
+void Precomputation::AddCollocations(
+    const vector<tuple<int, int, int> >& matchings, const vector<int>& data,
+    int max_rule_span, int min_gap_size, int max_rule_symbols) {
+  // Select the leftmost subpattern.
+  for (size_t i = 0; i < matchings.size(); ++i) {
+    int start1, size1, is_super1;
+    tie(start1, size1, is_super1) = matchings[i];
+
+    // Select the second (middle) subpattern
+    for (size_t j = i + 1; j < matchings.size(); ++j) {
+      int start2, size2, is_super2;
+      tie(start2, size2, is_super2) = matchings[j];
+      if (start2 - start1 >= max_rule_span) {
+        break;
+      }
+
+      if (start2 - start1 - size1 >= min_gap_size
+          && start2 + size2 - start1 <= max_rule_span
+          && size1 + size2 + 1 <= max_rule_symbols) {
+        vector<int> pattern(data.begin() + start1,
+            data.begin() + start1 + size1);
+        pattern.push_back(Precomputation::FIRST_NONTERMINAL);
+        pattern.insert(pattern.end(), data.begin() + start2,
+            data.begin() + start2 + size2);
+        AddStartPositions(collocations[pattern], start1, start2);
+
+        // Try extending the binary collocation to a ternary collocation.
+        if (is_super2) {
+          pattern.push_back(Precomputation::SECOND_NONTERMINAL);
+          // Select the rightmost subpattern.
+          for (size_t k = j + 1; k < matchings.size(); ++k) {
+            int start3, size3, is_super3;
+            tie(start3, size3, is_super3) = matchings[k];
+            if (start3 - start1 >= max_rule_span) {
+              break;
+            }
+
+            if (start3 - start2 - size2 >= min_gap_size
+                && start3 + size3 - start1 <= max_rule_span
+                && size1 + size2 + size3 + 2 <= max_rule_symbols
+                && (is_super1 || is_super3)) {
+              pattern.insert(pattern.end(), data.begin() + start3,
+                  data.begin() + start3 + size3);
+              AddStartPositions(collocations[pattern], start1, start2, start3);
+              pattern.erase(pattern.end() - size3);
+            }
+          }
+        }
+      }
+    }
+  }
+}
+
+void Precomputation::AddStartPositions(
+    vector<int>& positions, int pos1, int pos2) {
+  positions.push_back(pos1);
+  positions.push_back(pos2);
+}
+
+void Precomputation::AddStartPositions(
+    vector<int>& positions, int pos1, int pos2, int pos3) {
+  positions.push_back(pos1);
+  positions.push_back(pos2);
+  positions.push_back(pos3);
+}
+
+void Precomputation::WriteBinary(const fs::path& filepath) const {
+  FILE* file = fopen(filepath.string().c_str(), "w");
+
+  // TODO(pauldb): Refactor this code.
+  int size = collocations.size();
+  fwrite(&size, sizeof(int), 1, file);
+  for (auto entry: collocations) {
+    size = entry.first.size();
+    fwrite(&size, sizeof(int), 1, file);
+    fwrite(entry.first.data(), sizeof(int), size, file);
+
+    size = entry.second.size();
+    fwrite(&size, sizeof(int), 1, file);
+    fwrite(entry.second.data(), sizeof(int), size, file);
+  }
+}
+
+const Index& Precomputation::GetCollocations() const {
+  return collocations;
+}
+
+} // namespace extractor
diff --git a/extractor/precomputation.h b/extractor/precomputation.h
new file mode 100644
index 00000000..e3c4d26a
--- /dev/null
+++ b/extractor/precomputation.h
@@ -0,0 +1,80 @@
+#ifndef _PRECOMPUTATION_H_
+#define _PRECOMPUTATION_H_
+
+#include <memory>
+#include <unordered_map>
+#include <unordered_set>
+#include <tuple>
+#include <vector>
+
+#include <boost/filesystem.hpp>
+#include <boost/functional/hash.hpp>
+
+namespace fs = boost::filesystem;
+using namespace std;
+
+namespace extractor {
+
+typedef boost::hash<vector<int> > VectorHash;
+typedef unordered_map<vector<int>, vector<int>, VectorHash> Index;
+
+class SuffixArray;
+
+/**
+ * Data structure wrapping an index with all the occurrences of the most
+ * frequent discontiguous collocations in the source data.
+ *
+ * Let a, b, c be contiguous collocations. The index will contain an entry for
+ * every collocation of the form:
+ * - aXb, where a and b are frequent
+ * - aXbXc, where a and b are super-frequent and c is frequent or
+ *                b and c are super-frequent and a is frequent.
+ */
+class Precomputation {
+ public:
+  // Constructs the index using the suffix array.
+  Precomputation(
+      shared_ptr<SuffixArray> suffix_array, int num_frequent_patterns,
+      int num_super_frequent_patterns, int max_rule_span,
+      int max_rule_symbols, int min_gap_size,
+      int max_frequent_phrase_len, int min_frequency);
+
+  virtual ~Precomputation();
+
+  void WriteBinary(const fs::path& filepath) const;
+
+  // Returns a reference to the index.
+  virtual const Index& GetCollocations() const;
+
+  static int FIRST_NONTERMINAL;
+  static int SECOND_NONTERMINAL;
+
+ protected:
+  Precomputation();
+
+ private:
+  // Finds the most frequent contiguous collocations.
+  vector<vector<int> > FindMostFrequentPatterns(
+      shared_ptr<SuffixArray> suffix_array, const vector<int>& data,
+      int num_frequent_patterns, int max_frequent_phrase_len,
+      int min_frequency);
+
+  // Given the locations of the frequent contiguous collocations in a sentence,
+  // it adds new entries to the index for each discontiguous collocation
+  // matching the criteria specified in the class description.
+  void AddCollocations(
+      const vector<std::tuple<int, int, int> >& matchings, const vector<int>& data,
+      int max_rule_span, int min_gap_size, int max_rule_symbols);
+
+  // Adds an occurrence of a binary collocation.
+  void AddStartPositions(vector<int>& positions, int pos1, int pos2);
+
+  // Adds an occurrence of a ternary collocation.
+  void AddStartPositions(vector<int>& positions, int pos1, int pos2, int pos3);
+
+  Index collocations;
+};
+
+} // namespace extractor
+
+#endif
diff --git a/extractor/precomputation_test.cc b/extractor/precomputation_test.cc
new file mode 100644
index 00000000..363febb7
--- /dev/null
+++ b/extractor/precomputation_test.cc
@@ -0,0 +1,106 @@
+#include <gtest/gtest.h>
+
+#include <memory>
+#include <vector>
+
+#include "mocks/mock_data_array.h"
+#include "mocks/mock_suffix_array.h"
+#include "precomputation.h"
+
+using namespace std;
+using namespace ::testing;
+
+namespace extractor {
+namespace {
+
+class PrecomputationTest : public Test {
+ protected:
+  virtual void SetUp() {
+    data = {4, 2, 3, 5, 7, 2, 3, 5, 2, 3, 4, 2, 1};
+    data_array = make_shared<MockDataArray>();
+    EXPECT_CALL(*data_array, GetData()).WillRepeatedly(ReturnRef(data));
+
+    vector<int> suffixes{12, 8, 5, 1, 9, 6, 2, 0, 10, 7, 3, 4, 13};
+    vector<int> lcp{-1, 0, 2, 3, 1, 0, 1, 2, 0, 2, 0, 1, 0, 0};
+    suffix_array = make_shared<MockSuffixArray>();
+    EXPECT_CALL(*suffix_array, GetData()).WillRepeatedly(Return(data_array));
+    for (size_t i = 0; i < suffixes.size(); ++i) {
+      EXPECT_CALL(*suffix_array,
+                  GetSuffix(i)).WillRepeatedly(Return(suffixes[i]));
+    }
+    EXPECT_CALL(*suffix_array, BuildLCPArray()).WillRepeatedly(Return(lcp));
+  }
+
+  vector<int> data;
+  shared_ptr<MockDataArray> data_array;
+  shared_ptr<MockSuffixArray> suffix_array;
+};
+
+TEST_F(PrecomputationTest, TestCollocations) {
+  Precomputation precomputation(suffix_array, 3, 3, 10, 5, 1, 4, 2);
+  Index collocations = precomputation.GetCollocations();
+
+  vector<int> key = {2, 3, -1, 2};
+  vector<int> expected_value = {1, 5, 1, 8, 5, 8, 5, 11, 8, 11};
+  EXPECT_EQ(expected_value, collocations[key]);
+  key = {2, 3, -1, 2, 3};
+  expected_value = {1, 5, 1, 8, 5, 8};
+  EXPECT_EQ(expected_value, collocations[key]);
+  key = {2, 3, -1, 3};
+  expected_value = {1, 6, 1, 9, 5, 9};
+  EXPECT_EQ(expected_value, collocations[key]);
+  key = {3, -1, 2};
+  expected_value = {2, 5, 2, 8, 2, 11, 6, 8, 6, 11, 9, 11};
+  EXPECT_EQ(expected_value, collocations[key]);
+  key = {3, -1, 3};
+  expected_value = {2, 6, 2, 9, 6, 9};
+  EXPECT_EQ(expected_value, collocations[key]);
+  key = {3, -1, 2, 3};
+  expected_value = {2, 5, 2, 8, 6, 8};
+  EXPECT_EQ(expected_value, collocations[key]);
+  key = {2, -1, 2};
+  expected_value = {1, 5, 1, 8, 5, 8, 5, 11, 8, 11};
+  EXPECT_EQ(expected_value, collocations[key]);
+  key = {2, -1, 2, 3};
+  expected_value = {1, 5, 1, 8, 5, 8};
+  EXPECT_EQ(expected_value, collocations[key]);
+  key = {2, -1, 3};
+  expected_value = {1, 6, 1, 9, 5, 9};
+  EXPECT_EQ(expected_value, collocations[key]);
+
+  key = {2, -1, 2, -2, 2};
+  expected_value = {1, 5, 8, 5, 8, 11};
+  EXPECT_EQ(expected_value, collocations[key]);
+  key = {2, -1, 2, -2, 3};
+  expected_value = {1, 5, 9};
+  EXPECT_EQ(expected_value, collocations[key]);
+  key = {2, -1, 3, -2, 2};
+  expected_value = {1, 6, 8, 5, 9, 11};
+  EXPECT_EQ(expected_value, collocations[key]);
+  key = {2, -1, 3, -2, 3};
+  expected_value = {1, 6, 9};
+  EXPECT_EQ(expected_value, collocations[key]);
+  key = {3, -1, 2, -2, 2};
+  expected_value = {2, 5, 8, 2, 5, 11, 2, 8, 11, 6, 8, 11};
+  EXPECT_EQ(expected_value, collocations[key]);
+  key = {3, -1, 2, -2, 3};
+  expected_value = {2, 5, 9};
+  EXPECT_EQ(expected_value, collocations[key]);
+  key = {3, -1, 3, -2, 2};
+  expected_value = {2, 6, 8, 2, 6, 11, 2, 9, 11, 6, 9, 11};
+  EXPECT_EQ(expected_value, collocations[key]);
+  key = {3, -1, 3, -2, 3};
+  expected_value = {2, 6, 9};
+  EXPECT_EQ(expected_value, collocations[key]);
+
+  // Exceeds max_rule_symbols.
+  key = {2, -1, 2, -2, 2, 3};
+  EXPECT_EQ(0, collocations.count(key));
+  // Contains non frequent pattern.
+  key = {2, -1, 5};
+  EXPECT_EQ(0, collocations.count(key));
+}
+
+} // namespace
+} // namespace extractor
+
diff --git a/extractor/rule.cc b/extractor/rule.cc
new file mode 100644
index 00000000..b6c7d783
--- /dev/null
+++ b/extractor/rule.cc
@@ -0,0 +1,14 @@
+#include "rule.h"
+
+namespace extractor {
+
+Rule::Rule(const Phrase& source_phrase,
+           const Phrase& target_phrase,
+           const vector<double>& scores,
+           const vector<pair<int, int> >& alignment) :
+  source_phrase(source_phrase),
+  target_phrase(target_phrase),
+  scores(scores),
+  alignment(alignment) {}
+
+} // namespace extractor
diff --git a/extractor/rule.h b/extractor/rule.h
new file mode 100644
index 00000000..bc95709e
--- /dev/null
+++ b/extractor/rule.h
@@ -0,0 +1,27 @@
+#ifndef _RULE_H_
+#define _RULE_H_
+
+#include <vector>
+
+#include "phrase.h"
+
+using namespace std;
+
+namespace extractor {
+
+/**
+ * Structure containing the data for a SCFG rule.
+ */
+struct Rule {
+  Rule(const Phrase& source_phrase, const Phrase& target_phrase,
+       const vector<double>& scores, const vector<pair<int, int> >& alignment);
+
+  Phrase source_phrase;
+  Phrase target_phrase;
+  vector<double> scores;
+  vector<pair<int, int> > alignment;
+};
+
+} // namespace extractor
+
+#endif
diff --git a/extractor/rule_extractor.cc b/extractor/rule_extractor.cc
new file mode 100644
index 00000000..fa7386a4
--- /dev/null
+++ b/extractor/rule_extractor.cc
@@ -0,0 +1,343 @@
+#include "rule_extractor.h"
+
+#include <map>
+
+#include "alignment.h"
+#include "data_array.h"
+#include "features/feature.h"
+#include "phrase_builder.h"
+#include "phrase_location.h"
+#include "rule.h"
+#include "rule_extractor_helper.h"
+#include "scorer.h"
+#include "target_phrase_extractor.h"
+
+using namespace std;
+
+namespace extractor {
+
+RuleExtractor::RuleExtractor(
+    shared_ptr<DataArray> source_data_array,
+    shared_ptr<DataArray> target_data_array,
+    shared_ptr<Alignment> alignment,
+    shared_ptr<PhraseBuilder> phrase_builder,
+    shared_ptr<Scorer> scorer,
+    shared_ptr<Vocabulary> vocabulary,
+    int max_rule_span,
+    int min_gap_size,
+    int max_nonterminals,
+    int max_rule_symbols,
+    bool require_aligned_terminal,
+    bool require_aligned_chunks,
+    bool require_tight_phrases) :
+    target_data_array(target_data_array),
+    source_data_array(source_data_array),
+    phrase_builder(phrase_builder),
+    scorer(scorer),
+    max_rule_span(max_rule_span),
+    min_gap_size(min_gap_size),
+    max_nonterminals(max_nonterminals),
+    max_rule_symbols(max_rule_symbols),
+    require_tight_phrases(require_tight_phrases) {
+  helper = make_shared<RuleExtractorHelper>(
+      source_data_array, target_data_array, alignment, max_rule_span,
+      max_rule_symbols, require_aligned_terminal, require_aligned_chunks,
+      require_tight_phrases);
+  target_phrase_extractor = make_shared<TargetPhraseExtractor>(
+      target_data_array, alignment, phrase_builder, helper, vocabulary,
+      max_rule_span, require_tight_phrases);
+}
+
+RuleExtractor::RuleExtractor(
+    shared_ptr<DataArray> source_data_array,
+    shared_ptr<PhraseBuilder> phrase_builder,
+    shared_ptr<Scorer> scorer,
+    shared_ptr<TargetPhraseExtractor> target_phrase_extractor,
+    shared_ptr<RuleExtractorHelper> helper,
+    int max_rule_span,
+    int min_gap_size,
+    int max_nonterminals,
+    int max_rule_symbols,
+    bool require_tight_phrases) :
+    source_data_array(source_data_array),
+    phrase_builder(phrase_builder),
+    scorer(scorer),
+    target_phrase_extractor(target_phrase_extractor),
+    helper(helper),
+    max_rule_span(max_rule_span),
+    min_gap_size(min_gap_size),
+    max_nonterminals(max_nonterminals),
+    max_rule_symbols(max_rule_symbols),
+    require_tight_phrases(require_tight_phrases) {}
+
+RuleExtractor::RuleExtractor() {}
+
+RuleExtractor::~RuleExtractor() {}
+
+vector<Rule> RuleExtractor::ExtractRules(const Phrase& phrase,
+                                         const PhraseLocation& location) const {
+  int num_subpatterns = location.num_subpatterns;
+  vector<int> matchings = *location.matchings;
+
+  // Calculate statistics for the (sampled) occurrences of the source phrase.
+  map<Phrase, double> source_phrase_counter;
+  map<Phrase, map<Phrase, map<PhraseAlignment, int> > > alignments_counter;
+  for (auto i = matchings.begin(); i != matchings.end(); i += num_subpatterns) {
+    vector<int> matching(i, i + num_subpatterns);
+    vector<Extract> extracts = ExtractAlignments(phrase, matching);
+
+    for (Extract e: extracts) {
+      source_phrase_counter[e.source_phrase] += e.pairs_count;
+      alignments_counter[e.source_phrase][e.target_phrase][e.alignment] += 1;
+    }
+  }
+
+  // Compute the feature scores and find the most likely (frequent) alignment
+  // for each pair of source-target phrases.
+  int num_samples = matchings.size() / num_subpatterns;
+  vector<Rule> rules;
+  for (auto source_phrase_entry: alignments_counter) {
+    Phrase source_phrase = source_phrase_entry.first;
+    for (auto target_phrase_entry: source_phrase_entry.second) {
+      Phrase target_phrase = target_phrase_entry.first;
+
+      int max_locations = 0, num_locations = 0;
+      PhraseAlignment most_frequent_alignment;
+      for (auto alignment_entry: target_phrase_entry.second) {
+        num_locations += alignment_entry.second;
+        if (alignment_entry.second > max_locations) {
+          most_frequent_alignment = alignment_entry.first;
+          max_locations = alignment_entry.second;
+        }
+      }
+
+      features::FeatureContext context(source_phrase, target_phrase,
+          source_phrase_counter[source_phrase], num_locations, num_samples);
+      vector<double> scores = scorer->Score(context);
+      rules.push_back(Rule(source_phrase, target_phrase, scores,
+                           most_frequent_alignment));
+    }
+  }
+  return rules;
+}
+
+vector<Extract> RuleExtractor::ExtractAlignments(
+    const Phrase& phrase, const vector<int>& matching) const {
+  vector<Extract> extracts;
+  int sentence_id = source_data_array->GetSentenceId(matching[0]);
+  int source_sent_start = source_data_array->GetSentenceStart(sentence_id);
+
+  // Get the span in the opposite sentence for each word in the source-target
+  // sentece pair.
+  vector<int> source_low, source_high, target_low, target_high;
+  helper->GetLinksSpans(source_low, source_high, target_low, target_high,
+                        sentence_id);
+
+  int num_subpatterns = matching.size();
+  vector<int> chunklen(num_subpatterns);
+  for (size_t i = 0; i < num_subpatterns; ++i) {
+    chunklen[i] = phrase.GetChunkLen(i);
+  }
+
+  // Basic checks to see if we can extract phrase pairs for this occurrence.
+  if (!helper->CheckAlignedTerminals(matching, chunklen, source_low,
+                                     source_sent_start) ||
+      !helper->CheckTightPhrases(matching, chunklen, source_low,
+                                 source_sent_start)) {
+    return extracts;
+  }
+
+  int source_back_low = -1, source_back_high = -1;
+  int source_phrase_low = matching[0] - source_sent_start;
+  int source_phrase_high = matching.back() + chunklen.back() -
+                           source_sent_start;
+  int target_phrase_low = -1, target_phrase_high = -1;
+  // Find target span and reflected source span for the source phrase.
+  if (!helper->FindFixPoint(source_phrase_low, source_phrase_high, source_low,
+                            source_high, target_phrase_low, target_phrase_high,
+                            target_low, target_high, source_back_low,
+                            source_back_high, sentence_id, min_gap_size, 0,
+                            max_nonterminals - matching.size() + 1, true, true,
+                            false)) {
+    return extracts;
+  }
+
+  // Get spans for nonterminal gaps.
+  bool met_constraints = true;
+  int num_symbols = phrase.GetNumSymbols();
+  vector<pair<int, int> > source_gaps, target_gaps;
+  if (!helper->GetGaps(source_gaps, target_gaps, matching, chunklen, source_low,
+                       source_high, target_low, target_high, source_phrase_low,
+                       source_phrase_high, source_back_low, source_back_high,
+                       sentence_id, source_sent_start, num_symbols,
+                       met_constraints)) {
+    return extracts;
+  }
+
+  // Find target phrases aligned with the initial source phrase.
+  bool starts_with_x = source_back_low != source_phrase_low;
+  bool ends_with_x = source_back_high != source_phrase_high;
+  Phrase source_phrase = phrase_builder->Extend(
+      phrase, starts_with_x, ends_with_x);
+  unordered_map<int, int> source_indexes = helper->GetSourceIndexes(
+      matching, chunklen, starts_with_x, source_sent_start);
+  if (met_constraints) {
+    AddExtracts(extracts, source_phrase, source_indexes, target_gaps,
+                target_low, target_phrase_low, target_phrase_high, sentence_id);
+  }
+
+  if (source_gaps.size() >= max_nonterminals ||
+      source_phrase.GetNumSymbols() >= max_rule_symbols ||
+      source_back_high - source_back_low + min_gap_size > max_rule_span) {
+    // Cannot add any more nonterminals.
+    return extracts;
+  }
+
+  // Extend the source phrase by adding a leading and/or trailing nonterminal
+  // and find target phrases aligned with the extended source phrase.
+  for (int i = 0; i < 2; ++i) {
+    for (int j = 1 - i; j < 2; ++j) {
+      AddNonterminalExtremities(extracts, matching, chunklen, source_phrase,
+          source_back_low, source_back_high, source_low, source_high,
+          target_low, target_high, target_gaps, sentence_id, source_sent_start,
+          starts_with_x, ends_with_x, i, j);
+    }
+  }
+
+  return extracts;
+}
+
+void RuleExtractor::AddExtracts(
+    vector<Extract>& extracts, const Phrase& source_phrase,
+    const unordered_map<int, int>& source_indexes,
+    const vector<pair<int, int> >& target_gaps, const vector<int>& target_low,
+    int target_phrase_low, int target_phrase_high, int sentence_id) const {
+  auto target_phrases = target_phrase_extractor->ExtractPhrases(
+      target_gaps, target_low, target_phrase_low, target_phrase_high,
+      source_indexes, sentence_id);
+
+  if (target_phrases.size() > 0) {
+    // Split the probability equally across all target phrases that can be
+    // aligned with a single occurrence of the source phrase.
+    double pairs_count = 1.0 / target_phrases.size();
+    for (auto target_phrase: target_phrases) {
+      extracts.push_back(Extract(source_phrase, target_phrase.first,
+                                 pairs_count, target_phrase.second));
+    }
+  }
+}
+
+void RuleExtractor::AddNonterminalExtremities(
+    vector<Extract>& extracts, const vector<int>& matching,
+    const vector<int>& chunklen, const Phrase& source_phrase,
+    int source_back_low, int source_back_high, const vector<int>& source_low,
+    const vector<int>& source_high, const vector<int>& target_low,
+    const vector<int>& target_high, vector<pair<int, int> > target_gaps,
+    int sentence_id, int source_sent_start, int starts_with_x, int ends_with_x,
+    int extend_left, int extend_right) const {
+  int source_x_low = source_back_low, source_x_high = source_back_high;
+
+  // Check if the extended source phrase will remain tight.
+  if (require_tight_phrases) {
+    if (source_low[source_back_low - extend_left] == -1 ||
+        source_low[source_back_high + extend_right - 1] == -1) {
+      return;
+    }
+  }
+
+  // Check if we can add a nonterminal to the left.
+  if (extend_left) {
+    if (starts_with_x || source_back_low < min_gap_size) {
+      return;
+    }
+
+    source_x_low = source_back_low - min_gap_size;
+    if (require_tight_phrases) {
+      while (source_x_low >= 0 && source_low[source_x_low] == -1) {
+        --source_x_low;
+      }
+    }
+    if (source_x_low < 0) {
+      return;
+    }
+  }
+
+  // Check if we can add a nonterminal to the right.
+  if (extend_right) {
+    int source_sent_len = source_data_array->GetSentenceLength(sentence_id);
+    if (ends_with_x || source_back_high + min_gap_size > source_sent_len) {
+      return;
+    }
+    source_x_high = source_back_high + min_gap_size;
+    if (require_tight_phrases) {
+      while (source_x_high <= source_sent_len &&
+             source_low[source_x_high - 1] == -1) {
+        ++source_x_high;
+      }
+    }
+
+    if (source_x_high > source_sent_len) {
+      return;
+    }
+  }
+
+  // More length checks.
+  int new_nonterminals = extend_left + extend_right;
+  if (source_x_high - source_x_low > max_rule_span ||
+      target_gaps.size() + new_nonterminals > max_nonterminals ||
+      source_phrase.GetNumSymbols() + new_nonterminals > max_rule_symbols) {
+    return;
+  }
+
+  // Find the target span for the extended phrase and the reflected source span.
+  int target_x_low = -1, target_x_high = -1;
+  if (!helper->FindFixPoint(source_x_low, source_x_high, source_low,
+                            source_high, target_x_low, target_x_high,
+                            target_low, target_high, source_x_low,
+                            source_x_high, sentence_id, 1, 1,
+                            new_nonterminals, extend_left, extend_right,
+                            true)) {
+    return;
+  }
+
+  // Check gap integrity for the leading nonterminal.
+  if (extend_left) {
+    int source_gap_low = -1, source_gap_high = -1;
+    int target_gap_low = -1, target_gap_high = -1;
+    if ((require_tight_phrases && source_low[source_x_low] == -1) ||
+        !helper->FindFixPoint(source_x_low, source_back_low, source_low,
+                              source_high, target_gap_low, target_gap_high,
+                              target_low, target_high, source_gap_low,
+                              source_gap_high, sentence_id, 0, 0, 0, false,
+                              false, false)) {
+      return;
+    }
+    target_gaps.insert(target_gaps.begin(),
+                       make_pair(target_gap_low, target_gap_high));
+  }
+
+  // Check gap integrity for the trailing nonterminal.
+  if (extend_right) {
+    int target_gap_low = -1, target_gap_high = -1;
+    int source_gap_low = -1, source_gap_high = -1;
+    if ((require_tight_phrases && source_low[source_x_high - 1] == -1) ||
+        !helper->FindFixPoint(source_back_high, source_x_high, source_low,
+                              source_high, target_gap_low, target_gap_high,
+                              target_low, target_high, source_gap_low,
+                              source_gap_high, sentence_id, 0, 0, 0, false,
+                              false, false)) {
+      return;
+    }
+    target_gaps.push_back(make_pair(target_gap_low, target_gap_high));
+  }
+
+  // Find target phrases aligned with the extended source phrase.
+  Phrase new_source_phrase = phrase_builder->Extend(source_phrase, extend_left,
+                                                    extend_right);
+  unordered_map<int, int> source_indexes = helper->GetSourceIndexes(
+      matching, chunklen, extend_left || starts_with_x, source_sent_start);
+  AddExtracts(extracts, new_source_phrase, source_indexes, target_gaps,
+              target_low, target_x_low, target_x_high, sentence_id);
+}
+
+} // namespace extractor
diff --git a/extractor/rule_extractor.h b/extractor/rule_extractor.h
new file mode 100644
index 00000000..26e6f21c
--- /dev/null
+++ b/extractor/rule_extractor.h
@@ -0,0 +1,124 @@
+#ifndef _RULE_EXTRACTOR_H_
+#define _RULE_EXTRACTOR_H_
+
+#include <memory>
+#include <unordered_map>
+#include <vector>
+
+#include "phrase.h"
+
+using namespace std;
+
+namespace extractor {
+
+typedef vector<pair<int, int> > PhraseAlignment;
+
+class Alignment;
+class DataArray;
+class PhraseBuilder;
+class PhraseLocation;
+class Rule;
+class RuleExtractorHelper;
+class Scorer;
+class TargetPhraseExtractor;
+
+/**
+ * Structure containing data about the occurrences of a source-target phrase pair
+ * in the parallel corpus.
+ */
+struct Extract {
+  Extract(const Phrase& source_phrase, const Phrase& target_phrase,
+          double pairs_count, const PhraseAlignment& alignment) :
+      source_phrase(source_phrase), target_phrase(target_phrase),
+      pairs_count(pairs_count), alignment(alignment) {}
+
+  Phrase source_phrase;
+  Phrase target_phrase;
+  double pairs_count;
+  PhraseAlignment alignment;
+};
+
+/**
+ * Component for extracting SCFG rules.
+ */
+class RuleExtractor {
+ public:
+  RuleExtractor(shared_ptr<DataArray> source_data_array,
+                shared_ptr<DataArray> target_data_array,
+                shared_ptr<Alignment> alingment,
+                shared_ptr<PhraseBuilder> phrase_builder,
+                shared_ptr<Scorer> scorer,
+                shared_ptr<Vocabulary> vocabulary,
+                int min_gap_size,
+                int max_rule_span,
+                int max_nonterminals,
+                int max_rule_symbols,
+                bool require_aligned_terminal,
+                bool require_aligned_chunks,
+                bool require_tight_phrases);
+
+  // For testing only.
+  RuleExtractor(shared_ptr<DataArray> source_data_array,
+                shared_ptr<PhraseBuilder> phrase_builder,
+                shared_ptr<Scorer> scorer,
+                shared_ptr<TargetPhraseExtractor> target_phrase_extractor,
+                shared_ptr<RuleExtractorHelper> helper,
+                int max_rule_span,
+                int min_gap_size,
+                int max_nonterminals,
+                int max_rule_symbols,
+                bool require_tight_phrases);
+
+  virtual ~RuleExtractor();
+
+  // Extracts SCFG rules given a source phrase and a set of its occurrences
+  // in the source data.
+  virtual vector<Rule> ExtractRules(const Phrase& phrase,
+                                    const PhraseLocation& location) const;
+
+ protected:
+  RuleExtractor();
+
+ private:
+  // Finds all target phrases that can be aligned with the source phrase for a
+  // particular occurrence in the data.
+  vector<Extract> ExtractAlignments(const Phrase& phrase,
+                                    const vector<int>& matching) const;
+
+  // Extracts all target phrases for a given occurrence of the source phrase in
+  // the data. Constructs a vector of Extracts using these target phrases.
+  void AddExtracts(
+      vector<Extract>& extracts, const Phrase& source_phrase,
+      const unordered_map<int, int>& source_indexes,
+      const vector<pair<int, int> >& target_gaps, const vector<int>& target_low,
+      int target_phrase_low, int target_phrase_high, int sentence_id) const;
+
+  // Adds a leading and/or trailing nonterminal to the source phrase and
+  // extracts target phrases that can be aligned with the extended source
+  // phrase.
+  void AddNonterminalExtremities(
+      vector<Extract>& extracts, const vector<int>& matching,
+      const vector<int>& chunklen, const Phrase& source_phrase,
+      int source_back_low, int source_back_high, const vector<int>& source_low,
+      const vector<int>& source_high, const vector<int>& target_low,
+      const vector<int>& target_high, vector<pair<int, int> > target_gaps,
+      int sentence_id, int source_sent_start, int starts_with_x,
+      int ends_with_x, int extend_left, int extend_right) const;
+
+ private:
+  shared_ptr<DataArray> target_data_array;
+  shared_ptr<DataArray> source_data_array;
+  shared_ptr<PhraseBuilder> phrase_builder;
+  shared_ptr<Scorer> scorer;
+  shared_ptr<TargetPhraseExtractor> target_phrase_extractor;
+  shared_ptr<RuleExtractorHelper> helper;
+  int max_rule_span;
+  int min_gap_size;
+  int max_nonterminals;
+  int max_rule_symbols;
+  bool require_tight_phrases;
+};
+
+} // namespace extractor
+
+#endif
diff --git a/extractor/rule_extractor_helper.cc b/extractor/rule_extractor_helper.cc
new file mode 100644
index 00000000..8a9516f2
--- /dev/null
+++ b/extractor/rule_extractor_helper.cc
@@ -0,0 +1,362 @@
+#include "rule_extractor_helper.h"
+
+#include "data_array.h"
+#include "alignment.h"
+
+namespace extractor {
+
+RuleExtractorHelper::RuleExtractorHelper(
+    shared_ptr<DataArray> source_data_array,
+    shared_ptr<DataArray> target_data_array,
+    shared_ptr<Alignment> alignment,
+    int max_rule_span,
+    int max_rule_symbols,
+    bool require_aligned_terminal,
+    bool require_aligned_chunks,
+    bool require_tight_phrases) :
+    source_data_array(source_data_array),
+    target_data_array(target_data_array),
+    alignment(alignment),
+    max_rule_span(max_rule_span),
+    max_rule_symbols(max_rule_symbols),
+    require_aligned_terminal(require_aligned_terminal),
+    require_aligned_chunks(require_aligned_chunks),
+    require_tight_phrases(require_tight_phrases) {}
+
+RuleExtractorHelper::RuleExtractorHelper() {}
+
+RuleExtractorHelper::~RuleExtractorHelper() {}
+
+void RuleExtractorHelper::GetLinksSpans(
+    vector<int>& source_low, vector<int>& source_high,
+    vector<int>& target_low, vector<int>& target_high, int sentence_id) const {
+  int source_sent_len = source_data_array->GetSentenceLength(sentence_id);
+  int target_sent_len = target_data_array->GetSentenceLength(sentence_id);
+  source_low = vector<int>(source_sent_len, -1);
+  source_high = vector<int>(source_sent_len, -1);
+
+  target_low = vector<int>(target_sent_len, -1);
+  target_high = vector<int>(target_sent_len, -1);
+  vector<pair<int, int> > links = alignment->GetLinks(sentence_id);
+  for (auto link: links) {
+    if (source_low[link.first] == -1 || source_low[link.first] > link.second) {
+      source_low[link.first] = link.second;
+    }
+    source_high[link.first] = max(source_high[link.first], link.second + 1);
+
+    if (target_low[link.second] == -1 || target_low[link.second] > link.first) {
+      target_low[link.second] = link.first;
+    }
+    target_high[link.second] = max(target_high[link.second], link.first + 1);
+  }
+}
+
+bool RuleExtractorHelper::CheckAlignedTerminals(
+    const vector<int>& matching,
+    const vector<int>& chunklen,
+    const vector<int>& source_low,
+    int source_sent_start) const {
+  if (!require_aligned_terminal) {
+    return true;
+  }
+
+  int num_aligned_chunks = 0;
+  for (size_t i = 0; i < chunklen.size(); ++i) {
+    for (size_t j = 0; j < chunklen[i]; ++j) {
+      int sent_index = matching[i] - source_sent_start + j;
+      if (source_low[sent_index] != -1) {
+        ++num_aligned_chunks;
+        break;
+      }
+    }
+  }
+
+  if (num_aligned_chunks == 0) {
+    return false;
+  }
+
+  return !require_aligned_chunks || num_aligned_chunks == chunklen.size();
+}
+
+bool RuleExtractorHelper::CheckTightPhrases(
+    const vector<int>& matching,
+    const vector<int>& chunklen,
+    const vector<int>& source_low,
+    int source_sent_start) const {
+  if (!require_tight_phrases) {
+    return true;
+  }
+
+  // Check if the chunk extremities are aligned.
+  for (size_t i = 0; i + 1 < chunklen.size(); ++i) {
+    int gap_start = matching[i] + chunklen[i] - source_sent_start;
+    int gap_end = matching[i + 1] - 1 - source_sent_start;
+    if (source_low[gap_start] == -1 || source_low[gap_end] == -1) {
+      return false;
+    }
+  }
+
+  return true;
+}
+
+bool RuleExtractorHelper::FindFixPoint(
+    int source_phrase_low, int source_phrase_high,
+    const vector<int>& source_low, const vector<int>& source_high,
+    int& target_phrase_low, int& target_phrase_high,
+    const vector<int>& target_low, const vector<int>& target_high,
+    int& source_back_low, int& source_back_high, int sentence_id,
+    int min_source_gap_size, int min_target_gap_size,
+    int max_new_x, bool allow_low_x, bool allow_high_x,
+    bool allow_arbitrary_expansion) const {
+  int prev_target_low = target_phrase_low;
+  int prev_target_high = target_phrase_high;
+
+  FindProjection(source_phrase_low, source_phrase_high, source_low,
+                 source_high, target_phrase_low, target_phrase_high);
+
+  if (target_phrase_low == -1) {
+    // Note: Low priority corner case inherited from Adam's code:
+    // If w is unaligned, but we don't require aligned terminals, returning an
+    // error here prevents the extraction of the allowed rule
+    // X -> X_1 w X_2 / X_1 X_2
+    return false;
+  }
+
+  int source_sent_len = source_data_array->GetSentenceLength(sentence_id);
+  int target_sent_len = target_data_array->GetSentenceLength(sentence_id);
+  // Extend the target span to the left.
+  if (prev_target_low != -1 && target_phrase_low != prev_target_low) {
+    if (prev_target_low - target_phrase_low < min_target_gap_size) {
+      target_phrase_low = prev_target_low - min_target_gap_size;
+      if (target_phrase_low < 0) {
+        return false;
+      }
+    }
+  }
+
+  // Extend the target span to the right.
+  if (prev_target_high != -1 && target_phrase_high != prev_target_high) {
+    if (target_phrase_high - prev_target_high < min_target_gap_size) {
+      target_phrase_high = prev_target_high + min_target_gap_size;
+      if (target_phrase_high > target_sent_len) {
+        return false;
+      }
+    }
+  }
+
+  // Check target span length.
+  if (target_phrase_high - target_phrase_low > max_rule_span) {
+    return false;
+  }
+
+  // Find the initial reflected source span.
+  source_back_low = source_back_high = -1;
+  FindProjection(target_phrase_low, target_phrase_high, target_low, target_high,
+                 source_back_low, source_back_high);
+  int new_x = 0;
+  bool new_low_x = false, new_high_x = false;
+  while (true) {
+    source_back_low = min(source_back_low, source_phrase_low);
+    source_back_high = max(source_back_high, source_phrase_high);
+
+    // Stop if the reflected source span matches the previous source span.
+    if (source_back_low == source_phrase_low &&
+        source_back_high == source_phrase_high) {
+      return true;
+    }
+
+    if (!allow_low_x && source_back_low < source_phrase_low) {
+      // Extension on the left side not allowed.
+      return false;
+    }
+    if (!allow_high_x && source_back_high > source_phrase_high) {
+      // Extension on the right side not allowed.
+      return false;
+    }
+
+    // Extend left side.
+    if (source_back_low < source_phrase_low) {
+      if (new_low_x == false) {
+        if (new_x >= max_new_x) {
+          return false;
+        }
+        new_low_x = true;
+        ++new_x;
+      }
+      if (source_phrase_low - source_back_low < min_source_gap_size) {
+        source_back_low = source_phrase_low - min_source_gap_size;
+        if (source_back_low < 0) {
+          return false;
+        }
+      }
+    }
+
+    // Extend right side.
+    if (source_back_high > source_phrase_high) {
+      if (new_high_x == false) {
+        if (new_x >= max_new_x) {
+          return false;
+        }
+        new_high_x = true;
+        ++new_x;
+      }
+      if (source_back_high - source_phrase_high < min_source_gap_size) {
+        source_back_high = source_phrase_high + min_source_gap_size;
+        if (source_back_high > source_sent_len) {
+          return false;
+        }
+      }
+    }
+
+    if (source_back_high - source_back_low > max_rule_span) {
+      // Rule span too wide.
+      return false;
+    }
+
+    prev_target_low = target_phrase_low;
+    prev_target_high = target_phrase_high;
+    // Find the reflection including the left gap (if one was added).
+    FindProjection(source_back_low, source_phrase_low, source_low, source_high,
+                   target_phrase_low, target_phrase_high);
+    // Find the reflection including the right gap (if one was added).
+    FindProjection(source_phrase_high, source_back_high, source_low,
+                   source_high, target_phrase_low, target_phrase_high);
+    // Stop if the new re-reflected target span matches the previous target
+    // span.
+    if (prev_target_low == target_phrase_low &&
+        prev_target_high == target_phrase_high) {
+      return true;
+    }
+
+    if (!allow_arbitrary_expansion) {
+      // Arbitrary expansion not allowed.
+      return false;
+    }
+    if (target_phrase_high - target_phrase_low > max_rule_span) {
+      // Target side too wide.
+      return false;
+    }
+
+    source_phrase_low = source_back_low;
+    source_phrase_high = source_back_high;
+    // Re-reflect the target span.
+    FindProjection(target_phrase_low, prev_target_low, target_low, target_high,
+                   source_back_low, source_back_high);
+    FindProjection(prev_target_high, target_phrase_high, target_low,
+                   target_high, source_back_low, source_back_high);
+  }
+
+  return false;
+}
+
+void RuleExtractorHelper::FindProjection(
+    int source_phrase_low, int source_phrase_high,
+    const vector<int>& source_low, const vector<int>& source_high,
+    int& target_phrase_low, int& target_phrase_high) const {
+  for (size_t i = source_phrase_low; i < source_phrase_high; ++i) {
+    if (source_low[i] != -1) {
+      if (target_phrase_low == -1 || source_low[i] < target_phrase_low) {
+        target_phrase_low = source_low[i];
+      }
+      target_phrase_high = max(target_phrase_high, source_high[i]);
+    }
+  }
+}
+
+bool RuleExtractorHelper::GetGaps(
+     vector<pair<int, int> >& source_gaps, vector<pair<int, int> >& target_gaps,
+     const vector<int>& matching, const vector<int>& chunklen,
+     const vector<int>& source_low, const vector<int>& source_high,
+     const vector<int>& target_low, const vector<int>& target_high,
+     int source_phrase_low, int source_phrase_high, int source_back_low,
+     int source_back_high, int sentence_id, int source_sent_start,
+     int& num_symbols, bool& met_constraints) const {
+  if (source_back_low < source_phrase_low) {
+    source_gaps.push_back(make_pair(source_back_low, source_phrase_low));
+    if (num_symbols >= max_rule_symbols) {
+      // Source side contains too many symbols.
+      return false;
+    }
+    ++num_symbols;
+    if (require_tight_phrases && (source_low[source_back_low] == -1 ||
+        source_low[source_phrase_low - 1] == -1)) {
+      // Inside edges of preceding gap are not tight.
+      return false;
+    }
+  } else if (require_tight_phrases && source_low[source_phrase_low] == -1) {
+    // This is not a hard error. We can't extract this phrase, but we might
+    // still be able to extract a superphrase.
+    met_constraints = false;
+  }
+
+  for (size_t i = 0; i + 1 < chunklen.size(); ++i) {
+    int gap_start = matching[i] + chunklen[i] - source_sent_start;
+    int gap_end = matching[i + 1] - source_sent_start;
+    source_gaps.push_back(make_pair(gap_start, gap_end));
+  }
+
+  if (source_phrase_high < source_back_high) {
+    source_gaps.push_back(make_pair(source_phrase_high, source_back_high));
+    if (num_symbols >= max_rule_symbols) {
+      // Source side contains too many symbols.
+      return false;
+    }
+    ++num_symbols;
+    if (require_tight_phrases && (source_low[source_phrase_high] == -1 ||
+        source_low[source_back_high - 1] == -1)) {
+      // Inside edges of following gap are not tight.
+      return false;
+    }
+  } else if (require_tight_phrases &&
+             source_low[source_phrase_high - 1] == -1) {
+    // This is not a hard error. We can't extract this phrase, but we might
+    // still be able to extract a superphrase.
+    met_constraints = false;
+  }
+
+  target_gaps.resize(source_gaps.size(), make_pair(-1, -1));
+  for (size_t i = 0; i < source_gaps.size(); ++i) {
+    if (!FindFixPoint(source_gaps[i].first, source_gaps[i].second, source_low,
+                      source_high, target_gaps[i].first, target_gaps[i].second,
+                      target_low, target_high, source_gaps[i].first,
+                      source_gaps[i].second, sentence_id, 0, 0, 0, false, false,
+                      false)) {
+      // Gap fails integrity check.
+      return false;
+    }
+  }
+
+  return true;
+}
+
+vector<int> RuleExtractorHelper::GetGapOrder(
+    const vector<pair<int, int> >& gaps) const {
+  vector<int> gap_order(gaps.size());
+  for (size_t i = 0; i < gap_order.size(); ++i) {
+    for (size_t j = 0; j < i; ++j) {
+      if (gaps[gap_order[j]] < gaps[i]) {
+        ++gap_order[i];
+      } else {
+        ++gap_order[j];
+      }
+    }
+  }
+  return gap_order;
+}
+
+unordered_map<int, int> RuleExtractorHelper::GetSourceIndexes(
+    const vector<int>& matching, const vector<int>& chunklen,
+    int starts_with_x, int source_sent_start) const {
+ unordered_map<int, int> source_indexes;
+ int num_symbols = starts_with_x;
+ for (size_t i = 0; i < matching.size(); ++i) {
+   for (size_t j = 0; j < chunklen[i]; ++j) {
+     source_indexes[matching[i] + j - source_sent_start] = num_symbols;
+     ++num_symbols;
+   }
+   ++num_symbols;
+ }
+ return source_indexes;
+}
+
+} // namespace extractor
diff --git a/extractor/rule_extractor_helper.h b/extractor/rule_extractor_helper.h
new file mode 100644
index 00000000..d4ae45d4
--- /dev/null
+++ b/extractor/rule_extractor_helper.h
@@ -0,0 +1,101 @@
+#ifndef _RULE_EXTRACTOR_HELPER_H_
+#define _RULE_EXTRACTOR_HELPER_H_
+
+#include <memory>
+#include <unordered_map>
+#include <vector>
+
+using namespace std;
+
+namespace extractor {
+
+class Alignment;
+class DataArray;
+
+/**
+ * Helper class for extracting SCFG rules.
+ */
+class RuleExtractorHelper {
+ public:
+  RuleExtractorHelper(shared_ptr<DataArray> source_data_array,
+                      shared_ptr<DataArray> target_data_array,
+                      shared_ptr<Alignment> alignment,
+                      int max_rule_span,
+                      int max_rule_symbols,
+                      bool require_aligned_terminal,
+                      bool require_aligned_chunks,
+                      bool require_tight_phrases);
+
+  virtual ~RuleExtractorHelper();
+
+  // Find the alignment span for each word in the source target sentence pair.
+  virtual void GetLinksSpans(vector<int>& source_low, vector<int>& source_high,
+                             vector<int>& target_low, vector<int>& target_high,
+                             int sentence_id) const;
+
+  // Check if one chunk (all chunks) is aligned at least in one point.
+  virtual bool CheckAlignedTerminals(const vector<int>& matching,
+                                     const vector<int>& chunklen,
+                                     const vector<int>& source_low,
+                                     int source_sent_start) const;
+
+  // Check if the chunks are tight.
+  virtual bool CheckTightPhrases(const vector<int>& matching,
+                                 const vector<int>& chunklen,
+                                 const vector<int>& source_low,
+                                 int source_sent_start) const;
+
+  // Find the target span and the reflected source span for a source phrase
+  // occurrence.
+  virtual bool FindFixPoint(
+      int source_phrase_low, int source_phrase_high,
+      const vector<int>& source_low, const vector<int>& source_high,
+      int& target_phrase_low, int& target_phrase_high,
+      const vector<int>& target_low, const vector<int>& target_high,
+      int& source_back_low, int& source_back_high, int sentence_id,
+      int min_source_gap_size, int min_target_gap_size,
+      int max_new_x, bool allow_low_x, bool allow_high_x,
+      bool allow_arbitrary_expansion) const;
+
+  // Find the gap spans for each nonterminal in the source phrase.
+  virtual bool GetGaps(
+      vector<pair<int, int> >& source_gaps, vector<pair<int, int> >& target_gaps,
+      const vector<int>& matching, const vector<int>& chunklen,
+      const vector<int>& source_low, const vector<int>& source_high,
+      const vector<int>& target_low, const vector<int>& target_high,
+      int source_phrase_low, int source_phrase_high, int source_back_low,
+      int source_back_high, int sentence_id, int source_sent_start,
+      int& num_symbols, bool& met_constraints) const;
+
+  // Get the order of the nonterminals in the target phrase.
+  virtual vector<int> GetGapOrder(const vector<pair<int, int> >& gaps) const;
+
+  // Map each terminal symbol with its position in the source phrase.
+  virtual unordered_map<int, int> GetSourceIndexes(
+      const vector<int>& matching, const vector<int>& chunklen,
+      int starts_with_x, int source_sent_start) const;
+
+ protected:
+  RuleExtractorHelper();
+
+ private:
+  // Find the projection of a source phrase in the target sentence. May also be
+  // used to find the projection of a target phrase in the source sentence.
+  void FindProjection(
+      int source_phrase_low, int source_phrase_high,
+      const vector<int>& source_low, const vector<int>& source_high,
+      int& target_phrase_low, int& target_phrase_high) const;
+
+  shared_ptr<DataArray> source_data_array;
+  shared_ptr<DataArray> target_data_array;
+  shared_ptr<Alignment> alignment;
+  int max_rule_span;
+  int max_rule_symbols;
+  bool require_aligned_terminal;
+  bool require_aligned_chunks;
+  bool require_tight_phrases;
+};
+
+} // namespace extractor
+
+#endif
diff --git a/extractor/rule_extractor_helper_test.cc b/extractor/rule_extractor_helper_test.cc
new file mode 100644
index 00000000..9b82abb1
--- /dev/null
+++ b/extractor/rule_extractor_helper_test.cc
@@ -0,0 +1,645 @@
+#include <gtest/gtest.h>
+
+#include <memory>
+
+#include "mocks/mock_alignment.h"
+#include "mocks/mock_data_array.h"
+#include "rule_extractor_helper.h"
+
+using namespace std;
+using namespace ::testing;
+
+namespace extractor {
+namespace {
+
+class RuleExtractorHelperTest : public Test {
+ protected:
+  virtual void SetUp() {
+    source_data_array = make_shared<MockDataArray>();
+    EXPECT_CALL(*source_data_array, GetSentenceLength(_))
+        .WillRepeatedly(Return(12));
+
+    target_data_array = make_shared<MockDataArray>();
+    EXPECT_CALL(*target_data_array, GetSentenceLength(_))
+        .WillRepeatedly(Return(12));
+
+    vector<pair<int, int> > links = {
+      make_pair(0, 0), make_pair(0, 1), make_pair(2, 2), make_pair(3, 1)
+    };
+    alignment = make_shared<MockAlignment>();
+    EXPECT_CALL(*alignment, GetLinks(_)).WillRepeatedly(Return(links));
+  }
+
+  shared_ptr<MockDataArray> source_data_array;
+  shared_ptr<MockDataArray> target_data_array;
+  shared_ptr<MockAlignment> alignment;
+  shared_ptr<RuleExtractorHelper> helper;
+};
+
+TEST_F(RuleExtractorHelperTest, TestGetLinksSpans) {
+  helper = make_shared<RuleExtractorHelper>(source_data_array,
+      target_data_array, alignment, 10, 5, true, true, true);
+  EXPECT_CALL(*source_data_array, GetSentenceLength(_))
+      .WillRepeatedly(Return(4));
+  EXPECT_CALL(*target_data_array, GetSentenceLength(_))
+      .WillRepeatedly(Return(3));
+
+  vector<int> source_low, source_high, target_low, target_high;
+  helper->GetLinksSpans(source_low, source_high, target_low, target_high, 0);
+
+  vector<int> expected_source_low = {0, -1, 2, 1};
+  EXPECT_EQ(expected_source_low, source_low);
+  vector<int> expected_source_high = {2, -1, 3, 2};
+  EXPECT_EQ(expected_source_high, source_high);
+  vector<int> expected_target_low = {0, 0, 2};
+  EXPECT_EQ(expected_target_low, target_low);
+  vector<int> expected_target_high = {1, 4, 3};
+  EXPECT_EQ(expected_target_high, target_high);
+}
+
+TEST_F(RuleExtractorHelperTest, TestCheckAlignedFalse) {
+  helper = make_shared<RuleExtractorHelper>(source_data_array,
+      target_data_array, alignment, 10, 5, false, false, true);
+  EXPECT_CALL(*source_data_array, GetSentenceId(_)).Times(0);
+  EXPECT_CALL(*source_data_array, GetSentenceStart(_)).Times(0);
+
+  vector<int> matching, chunklen, source_low;
+  EXPECT_TRUE(helper->CheckAlignedTerminals(matching, chunklen,
+                                            source_low, 10));
+}
+
+TEST_F(RuleExtractorHelperTest, TestCheckAlignedTerminal) {
+  helper = make_shared<RuleExtractorHelper>(source_data_array,
+      target_data_array, alignment, 10, 5, true, false, true);
+
+  vector<int> matching = {10, 12};
+  vector<int> chunklen = {1, 3};
+  vector<int> source_low = {-1, 1, -1, 3, -1};
+  EXPECT_TRUE(helper->CheckAlignedTerminals(matching, chunklen,
+                                            source_low, 10));
+  source_low = {-1, 1, -1, -1, -1};
+  EXPECT_FALSE(helper->CheckAlignedTerminals(matching, chunklen,
+                                             source_low, 10));
+}
+
+TEST_F(RuleExtractorHelperTest, TestCheckAlignedChunks) {
+  helper = make_shared<RuleExtractorHelper>(source_data_array,
+      target_data_array, alignment, 10, 5, true, true, true);
+
+  vector<int> matching = {10, 12};
+  vector<int> chunklen = {1, 3};
+  vector<int> source_low = {2, 1, -1, 3, -1};
+  EXPECT_TRUE(helper->CheckAlignedTerminals(matching, chunklen,
+                                            source_low, 10));
+  source_low = {-1, 1, -1, 3, -1};
+  EXPECT_FALSE(helper->CheckAlignedTerminals(matching, chunklen,
+                                             source_low, 10));
+  source_low = {2, 1, -1, -1, -1};
+  EXPECT_FALSE(helper->CheckAlignedTerminals(matching, chunklen,
+                                             source_low, 10));
+}
+
+
+TEST_F(RuleExtractorHelperTest, TestCheckTightPhrasesFalse) {
+  helper = make_shared<RuleExtractorHelper>(source_data_array,
+      target_data_array, alignment, 10, 5, true, true, false);
+  EXPECT_CALL(*source_data_array, GetSentenceId(_)).Times(0);
+  EXPECT_CALL(*source_data_array, GetSentenceStart(_)).Times(0);
+
+  vector<int> matching, chunklen, source_low;
+  EXPECT_TRUE(helper->CheckTightPhrases(matching, chunklen, source_low, 10));
+}
+
+TEST_F(RuleExtractorHelperTest, TestCheckTightPhrases) {
+  helper = make_shared<RuleExtractorHelper>(source_data_array,
+      target_data_array, alignment, 10, 5, true, true, true);
+
+  vector<int> matching = {10, 14, 18};
+  vector<int> chunklen = {2, 3, 1};
+  // No missing links.
+  vector<int> source_low = {0, 1, 2, 3, 4, 5, 6, 7, 8};
+  EXPECT_TRUE(helper->CheckTightPhrases(matching, chunklen, source_low, 10));
+
+  // Missing link at the beginning or ending of a gap.
+  source_low = {0, 1, -1, 3, 4, 5, 6, 7, 8};
+  EXPECT_FALSE(helper->CheckTightPhrases(matching, chunklen, source_low, 10));
+  source_low = {0, 1, 2, -1, 4, 5, 6, 7, 8};
+  EXPECT_FALSE(helper->CheckTightPhrases(matching, chunklen, source_low, 10));
+  source_low = {0, 1, 2, 3, 4, 5, 6, -1, 8};
+  EXPECT_FALSE(helper->CheckTightPhrases(matching, chunklen, source_low, 10));
+
+  // Missing link inside the gap.
+  chunklen = {1, 3, 1};
+  source_low = {0, 1, -1, 3, 4, 5, 6, 7, 8};
+  EXPECT_TRUE(helper->CheckTightPhrases(matching, chunklen, source_low, 10));
+}
+
+TEST_F(RuleExtractorHelperTest, TestFindFixPointBadEdgeCase) {
+  helper = make_shared<RuleExtractorHelper>(source_data_array,
+      target_data_array, alignment, 10, 5, true, true, true);
+
+  vector<int> source_low = {0, -1, 2};
+  vector<int> source_high = {1, -1, 3};
+  vector<int> target_low = {0, -1, 2};
+  vector<int> target_high = {1, -1, 3};
+  int source_phrase_low = 1, source_phrase_high = 2;
+  int source_back_low, source_back_high;
+  int target_phrase_low = -1, target_phrase_high = 1;
+
+  // This should be in fact true. See comment about the inherited bug.
+  EXPECT_FALSE(helper->FindFixPoint(source_phrase_low, source_phrase_high,
+                                    source_low, source_high, target_phrase_low,
+                                    target_phrase_high, target_low, target_high,
+                                    source_back_low, source_back_high, 0, 0, 0,
+                                    0, false, false, false));
+}
+
+TEST_F(RuleExtractorHelperTest, TestFindFixPointTargetSentenceOutOfBounds) {
+  helper = make_shared<RuleExtractorHelper>(source_data_array,
+      target_data_array, alignment, 10, 5, true, true, true);
+  EXPECT_CALL(*source_data_array, GetSentenceLength(_))
+      .WillRepeatedly(Return(3));
+  EXPECT_CALL(*target_data_array, GetSentenceLength(_))
+      .WillRepeatedly(Return(3));
+
+  vector<int> source_low = {0, 0, 2};
+  vector<int> source_high = {1, 2, 3};
+  vector<int> target_low = {0, 1, 2};
+  vector<int> target_high = {2, 2, 3};
+  int source_phrase_low = 1, source_phrase_high = 2;
+  int source_back_low, source_back_high;
+  int target_phrase_low = 1, target_phrase_high = 2;
+
+  // Extend out of sentence to left.
+  EXPECT_FALSE(helper->FindFixPoint(source_phrase_low, source_phrase_high,
+                                    source_low, source_high, target_phrase_low,
+                                    target_phrase_high, target_low, target_high,
+                                    source_back_low, source_back_high, 0, 2, 2,
+                                    0, false, false, false));
+  source_low = {0, 1, 2};
+  source_high = {1, 3, 3};
+  target_low = {0, 1, 1};
+  target_high = {1, 2, 3};
+  EXPECT_FALSE(helper->FindFixPoint(source_phrase_low, source_phrase_high,
+                                    source_low, source_high, target_phrase_low,
+                                    target_phrase_high, target_low, target_high,
+                                    source_back_low, source_back_high, 0, 2, 2,
+                                    0, false, false, false));
+}
+
+TEST_F(RuleExtractorHelperTest, TestFindFixPointTargetTooWide) {
+  helper = make_shared<RuleExtractorHelper>(source_data_array,
+      target_data_array, alignment, 5, 5, true, true, true);
+  EXPECT_CALL(*source_data_array, GetSentenceLength(_))
+      .WillRepeatedly(Return(7));
+  EXPECT_CALL(*target_data_array, GetSentenceLength(_))
+      .WillRepeatedly(Return(7));
+
+  vector<int> source_low = {0, 0, 0, 0, 0, 0, 0};
+  vector<int> source_high = {7, 7, 7, 7, 7, 7, 7};
+  vector<int> target_low = {0, -1, -1, -1, -1, -1, 0};
+  vector<int> target_high = {7, -1, -1, -1, -1, -1, 7};
+  int source_phrase_low = 2, source_phrase_high = 5;
+  int source_back_low, source_back_high;
+  int target_phrase_low = -1, target_phrase_high = -1;
+
+  // Projection is too wide.
+  EXPECT_FALSE(helper->FindFixPoint(source_phrase_low, source_phrase_high,
+                                    source_low, source_high, target_phrase_low,
+                                    target_phrase_high, target_low, target_high,
+                                    source_back_low, source_back_high, 0, 1, 1,
+                                    0, false, false, false));
+}
+
+TEST_F(RuleExtractorHelperTest, TestFindFixPoint) {
+  helper = make_shared<RuleExtractorHelper>(source_data_array,
+      target_data_array, alignment, 10, 5, true, true, true);
+  EXPECT_CALL(*source_data_array, GetSentenceLength(_))
+      .WillRepeatedly(Return(7));
+  EXPECT_CALL(*target_data_array, GetSentenceLength(_))
+      .WillRepeatedly(Return(7));
+
+  vector<int> source_low = {1, 1, 1, 3, 4, 5, 5};
+  vector<int> source_high = {2, 2, 3, 4, 6, 6, 6};
+  vector<int> target_low = {-1, 0, 2, 3, 4, 4, -1};
+  vector<int> target_high = {-1, 3, 3, 4, 5, 7, -1};
+  int source_phrase_low = 2, source_phrase_high = 5;
+  int source_back_low, source_back_high;
+  int target_phrase_low = 2, target_phrase_high = 5;
+
+  EXPECT_TRUE(helper->FindFixPoint(source_phrase_low, source_phrase_high,
+                                   source_low, source_high, target_phrase_low,
+                                   target_phrase_high, target_low, target_high,
+                                   source_back_low, source_back_high, 1, 1, 1,
+                                   2, true, true, false));
+  EXPECT_EQ(1, target_phrase_low);
+  EXPECT_EQ(6, target_phrase_high);
+  EXPECT_EQ(0, source_back_low);
+  EXPECT_EQ(7, source_back_high);
+
+  source_low = {0, -1, 1, 3, 4, -1, 6};
+  source_high = {1, -1, 3, 4, 6, -1, 7};
+  target_low = {0, 2, 2, 3, 4, 4, 6};
+  target_high = {1, 3, 3, 4, 5, 5, 7};
+  source_phrase_low = 2, source_phrase_high = 5;
+  target_phrase_low = -1, target_phrase_high = -1;
+  EXPECT_TRUE(helper->FindFixPoint(source_phrase_low, source_phrase_high,
+                                   source_low, source_high, target_phrase_low,
+                                   target_phrase_high, target_low, target_high,
+                                   source_back_low, source_back_high, 1, 1, 1,
+                                   2, true, true, false));
+  EXPECT_EQ(1, target_phrase_low);
+  EXPECT_EQ(6, target_phrase_high);
+  EXPECT_EQ(2, source_back_low);
+  EXPECT_EQ(5, source_back_high);
+}
+
+TEST_F(RuleExtractorHelperTest, TestFindFixPointExtensionsNotAllowed) {
+  helper = make_shared<RuleExtractorHelper>(source_data_array,
+      target_data_array, alignment, 10, 5, true, true, true);
+  EXPECT_CALL(*source_data_array, GetSentenceLength(_))
+      .WillRepeatedly(Return(3));
+  EXPECT_CALL(*target_data_array, GetSentenceLength(_))
+      .WillRepeatedly(Return(3));
+
+  vector<int> source_low = {0, 0, 2};
+  vector<int> source_high = {1, 2, 3};
+  vector<int> target_low = {0, 1, 2};
+  vector<int> target_high = {2, 2, 3};
+  int source_phrase_low = 1, source_phrase_high = 2;
+  int source_back_low, source_back_high;
+  int target_phrase_low = -1, target_phrase_high = -1;
+
+  // Extension on the left side not allowed.
+  EXPECT_FALSE(helper->FindFixPoint(source_phrase_low, source_phrase_high,
+                                    source_low, source_high, target_phrase_low,
+                                    target_phrase_high, target_low, target_high,
+                                    source_back_low, source_back_high, 0, 1, 1,
+                                    1, false, true, false));
+  // Extension on the left side is allowed, but we can't add anymore X.
+  target_phrase_low = -1, target_phrase_high = -1;
+  EXPECT_FALSE(helper->FindFixPoint(source_phrase_low, source_phrase_high,
+                                    source_low, source_high, target_phrase_low,
+                                    target_phrase_high, target_low, target_high,
+                                    source_back_low, source_back_high, 0, 1, 1,
+                                    0, true, true, false));
+  source_low = {0, 1, 2};
+  source_high = {1, 3, 3};
+  target_low = {0, 1, 1};
+  target_high = {1, 2, 3};
+  // Extension on the right side not allowed.
+  target_phrase_low = -1, target_phrase_high = -1;
+  EXPECT_FALSE(helper->FindFixPoint(source_phrase_low, source_phrase_high,
+                                    source_low, source_high, target_phrase_low,
+                                    target_phrase_high, target_low, target_high,
+                                    source_back_low, source_back_high, 0, 1, 1,
+                                    1, true, false, false));
+  // Extension on the right side is allowed, but we can't add anymore X.
+  target_phrase_low = -1, target_phrase_high = -1;
+  EXPECT_FALSE(helper->FindFixPoint(source_phrase_low, source_phrase_high,
+                                    source_low, source_high, target_phrase_low,
+                                    target_phrase_high, target_low, target_high,
+                                    source_back_low, source_back_high, 0, 1, 1,
+                                    0, true, true, false));
+}
+
+TEST_F(RuleExtractorHelperTest, TestFindFixPointSourceSentenceOutOfBounds) {
+  helper = make_shared<RuleExtractorHelper>(source_data_array,
+      target_data_array, alignment, 10, 5, true, true, true);
+  EXPECT_CALL(*source_data_array, GetSentenceLength(_))
+      .WillRepeatedly(Return(3));
+  EXPECT_CALL(*target_data_array, GetSentenceLength(_))
+      .WillRepeatedly(Return(3));
+
+  vector<int> source_low = {0, 0, 2};
+  vector<int> source_high = {1, 2, 3};
+  vector<int> target_low = {0, 1, 2};
+  vector<int> target_high = {2, 2, 3};
+  int source_phrase_low = 1, source_phrase_high = 2;
+  int source_back_low, source_back_high;
+  int target_phrase_low = 1, target_phrase_high = 2;
+  // Extend out of sentence to left.
+  EXPECT_FALSE(helper->FindFixPoint(source_phrase_low, source_phrase_high,
+                                    source_low, source_high, target_phrase_low,
+                                    target_phrase_high, target_low, target_high,
+                                    source_back_low, source_back_high, 0, 2, 1,
+                                    1, true, true, false));
+  source_low = {0, 1, 2};
+  source_high = {1, 3, 3};
+  target_low = {0, 1, 1};
+  target_high = {1, 2, 3};
+  target_phrase_low = 1, target_phrase_high = 2;
+  EXPECT_FALSE(helper->FindFixPoint(source_phrase_low, source_phrase_high,
+                                    source_low, source_high, target_phrase_low,
+                                    target_phrase_high, target_low, target_high,
+                                    source_back_low, source_back_high, 0, 2, 1,
+                                    1, true, true, false));
+}
+
+TEST_F(RuleExtractorHelperTest, TestFindFixPointTargetSourceWide) {
+  helper = make_shared<RuleExtractorHelper>(source_data_array,
+      target_data_array, alignment, 5, 5, true, true, true);
+  EXPECT_CALL(*source_data_array, GetSentenceLength(_))
+      .WillRepeatedly(Return(7));
+  EXPECT_CALL(*target_data_array, GetSentenceLength(_))
+      .WillRepeatedly(Return(7));
+
+  vector<int> source_low = {2, -1, 2, 3, 4, -1, 4};
+  vector<int> source_high = {3, -1, 3, 4, 5, -1, 5};
+  vector<int> target_low = {-1, -1, 0, 3, 4, -1, -1};
+  vector<int> target_high = {-1, -1, 3, 4, 7, -1, -1};
+  int source_phrase_low = 2, source_phrase_high = 5;
+  int source_back_low, source_back_high;
+  int target_phrase_low = -1, target_phrase_high = -1;
+
+  // Second projection (on source side) is too wide.
+  EXPECT_FALSE(helper->FindFixPoint(source_phrase_low, source_phrase_high,
+                                    source_low, source_high, target_phrase_low,
+                                    target_phrase_high, target_low, target_high,
+                                    source_back_low, source_back_high, 0, 1, 1,
+                                    2, true, true, false));
+}
+
+TEST_F(RuleExtractorHelperTest, TestFindFixPointArbitraryExpansion) {
+  helper = make_shared<RuleExtractorHelper>(source_data_array,
+      target_data_array, alignment, 20, 5, true, true, true);
+  EXPECT_CALL(*source_data_array, GetSentenceLength(_))
+      .WillRepeatedly(Return(11));
+  EXPECT_CALL(*target_data_array, GetSentenceLength(_))
+      .WillRepeatedly(Return(11));
+
+  vector<int> source_low = {1, 1, 2, 3, 4, 5, 6, 7, 7, 8, 9};
+  vector<int> source_high = {2, 3, 4, 5, 5, 6, 7, 8, 9, 10, 10};
+  vector<int> target_low = {-1, 0, 1, 2, 3, 5, 6, 7, 8, 9, -1};
+  vector<int> target_high = {-1, 2, 3, 4, 5, 6, 8, 9, 10, 11, -1};
+  int source_phrase_low = 4, source_phrase_high = 7;
+  int source_back_low, source_back_high;
+  int target_phrase_low = -1, target_phrase_high = -1;
+  EXPECT_FALSE(helper->FindFixPoint(source_phrase_low, source_phrase_high,
+                                    source_low, source_high, target_phrase_low,
+                                    target_phrase_high, target_low, target_high,
+                                    source_back_low, source_back_high, 0, 1, 1,
+                                    10, true, true, false));
+
+  source_phrase_low = 4, source_phrase_high = 7;
+  target_phrase_low = -1, target_phrase_high = -1;
+  EXPECT_TRUE(helper->FindFixPoint(source_phrase_low, source_phrase_high,
+                                   source_low, source_high, target_phrase_low,
+                                   target_phrase_high, target_low, target_high,
+                                   source_back_low, source_back_high, 0, 1, 1,
+                                   10, true, true, true));
+}
+
+TEST_F(RuleExtractorHelperTest, TestGetGapOrder) {
+  helper = make_shared<RuleExtractorHelper>(source_data_array,
+      target_data_array, alignment, 10, 5, true, true, true);
+
+  vector<pair<int, int> > gaps =
+      {make_pair(0, 3), make_pair(5, 8), make_pair(11, 12), make_pair(15, 17)};
+  vector<int> expected_gap_order = {0, 1, 2, 3};
+  EXPECT_EQ(expected_gap_order, helper->GetGapOrder(gaps));
+
+  gaps = {make_pair(15, 17), make_pair(8, 9), make_pair(5, 6), make_pair(0, 3)};
+  expected_gap_order = {3, 2, 1, 0};
+  EXPECT_EQ(expected_gap_order, helper->GetGapOrder(gaps));
+
+  gaps = {make_pair(8, 9), make_pair(5, 6), make_pair(0, 3), make_pair(15, 17)};
+  expected_gap_order = {2, 1, 0, 3};
+  EXPECT_EQ(expected_gap_order, helper->GetGapOrder(gaps));
+}
+
+TEST_F(RuleExtractorHelperTest, TestGetGapsExceedNumSymbols) {
+  helper = make_shared<RuleExtractorHelper>(source_data_array,
+      target_data_array, alignment, 10, 5, true, true, true);
+  EXPECT_CALL(*source_data_array, GetSentenceLength(_))
+      .WillRepeatedly(Return(7));
+  EXPECT_CALL(*target_data_array, GetSentenceLength(_))
+      .WillRepeatedly(Return(7));
+
+  bool met_constraints = true;
+  vector<int> source_low = {1, 1, 2, 3, 4, 5, 6};
+  vector<int> source_high = {2, 2, 3, 4, 5, 6, 7};
+  vector<int> target_low = {-1, 0, 2, 3, 4, 5, 6};
+  vector<int> target_high = {-1, 2, 3, 4, 5, 6, 7};
+  int source_phrase_low = 1, source_phrase_high = 6;
+  int source_back_low = 0, source_back_high = 6;
+  vector<int> matching = {11, 13, 15};
+  vector<int> chunklen = {1, 1, 1};
+  vector<pair<int, int> > source_gaps, target_gaps;
+  int num_symbols = 5;
+  EXPECT_FALSE(helper->GetGaps(source_gaps, target_gaps, matching, chunklen,
+                               source_low, source_high, target_low, target_high,
+                               source_phrase_low, source_phrase_high,
+                               source_back_low, source_back_high, 5, 10,
+                               num_symbols, met_constraints));
+
+  source_low = {0, 1, 2, 3, 4, 5, 5};
+  source_high = {1, 2, 3, 4, 5, 6, 6};
+  target_low = {0, 1, 2, 3, 4, 5, -1};
+  target_high = {1, 2, 3, 4, 5, 7, -1};
+  source_phrase_low = 1, source_phrase_high = 6;
+  source_back_low = 1, source_back_high = 7;
+  num_symbols = 5;
+  EXPECT_FALSE(helper->GetGaps(source_gaps, target_gaps, matching, chunklen,
+                               source_low, source_high, target_low, target_high,
+                               source_phrase_low, source_phrase_high,
+                               source_back_low, source_back_high, 5, 10,
+                               num_symbols, met_constraints));
+}
+
+TEST_F(RuleExtractorHelperTest, TestGetGapsExtensionsNotTight) {
+  helper = make_shared<RuleExtractorHelper>(source_data_array,
+      target_data_array, alignment, 10, 7, true, true, true);
+  EXPECT_CALL(*source_data_array, GetSentenceLength(_))
+      .WillRepeatedly(Return(7));
+  EXPECT_CALL(*target_data_array, GetSentenceLength(_))
+      .WillRepeatedly(Return(7));
+
+  bool met_constraints = true;
+  vector<int> source_low = {-1, 1, 2, 3, 4, 5, -1};
+  vector<int> source_high = {-1, 2, 3, 4, 5, 6, -1};
+  vector<int> target_low = {-1, 1, 2, 3, 4, 5, -1};
+  vector<int> target_high = {-1, 2, 3, 4, 5, 6, -1};
+  int source_phrase_low = 1, source_phrase_high = 6;
+  int source_back_low = 0, source_back_high = 6;
+  vector<int> matching = {11, 13, 15};
+  vector<int> chunklen = {1, 1, 1};
+  vector<pair<int, int> > source_gaps, target_gaps;
+  int num_symbols = 5;
+  EXPECT_FALSE(helper->GetGaps(source_gaps, target_gaps, matching, chunklen,
+                               source_low, source_high, target_low, target_high,
+                               source_phrase_low, source_phrase_high,
+                               source_back_low, source_back_high, 5, 10,
+                               num_symbols, met_constraints));
+
+  source_phrase_low = 1, source_phrase_high = 6;
+  source_back_low = 1, source_back_high = 7;
+  num_symbols = 5;
+  EXPECT_FALSE(helper->GetGaps(source_gaps, target_gaps, matching, chunklen,
+                               source_low, source_high, target_low, target_high,
+                               source_phrase_low, source_phrase_high,
+                               source_back_low, source_back_high, 5, 10,
+                               num_symbols, met_constraints));
+}
+
+TEST_F(RuleExtractorHelperTest, TestGetGapsNotTightExtremities) {
+  helper = make_shared<RuleExtractorHelper>(source_data_array,
+      target_data_array, alignment, 10, 7, true, true, true);
+  EXPECT_CALL(*source_data_array, GetSentenceLength(_))
+      .WillRepeatedly(Return(7));
+  EXPECT_CALL(*target_data_array, GetSentenceLength(_))
+      .WillRepeatedly(Return(7));
+
+  bool met_constraints = true;
+  vector<int> source_low = {-1, -1, 2, 3, 4, 5, 6};
+  vector<int> source_high = {-1, -1, 3, 4, 5, 6, 7};
+  vector<int> target_low = {-1, -1, 2, 3, 4, 5, 6};
+  vector<int> target_high = {-1, -1, 3, 4, 5, 6, 7};
+  int source_phrase_low = 1, source_phrase_high = 6;
+  int source_back_low = 1, source_back_high = 6;
+  vector<int> matching = {11, 13, 15};
+  vector<int> chunklen = {1, 1, 1};
+  vector<pair<int, int> > source_gaps, target_gaps;
+  int num_symbols = 5;
+  EXPECT_TRUE(helper->GetGaps(source_gaps, target_gaps, matching, chunklen,
+                              source_low, source_high, target_low, target_high,
+                              source_phrase_low, source_phrase_high,
+                              source_back_low, source_back_high, 5, 10,
+                              num_symbols, met_constraints));
+  EXPECT_FALSE(met_constraints);
+  vector<pair<int, int> > expected_gaps = {make_pair(2, 3), make_pair(4, 5)};
+  EXPECT_EQ(expected_gaps, source_gaps);
+  EXPECT_EQ(expected_gaps, target_gaps);
+
+  source_low = {-1, 1, 2, 3, 4, -1, 6};
+  source_high = {-1, 2, 3, 4, 5, -1, 7};
+  target_low = {-1, 1, 2, 3, 4, -1, 6};
+  target_high = {-1, 2, 3, 4, 5, -1, 7};
+  met_constraints = true;
+  source_gaps.clear();
+  target_gaps.clear();
+  EXPECT_TRUE(helper->GetGaps(source_gaps, target_gaps, matching, chunklen,
+                              source_low, source_high, target_low, target_high,
+                              source_phrase_low, source_phrase_high,
+                              source_back_low, source_back_high, 5, 10,
+                              num_symbols, met_constraints));
+  EXPECT_FALSE(met_constraints);
+  EXPECT_EQ(expected_gaps, source_gaps);
+  EXPECT_EQ(expected_gaps, target_gaps);
+}
+
+TEST_F(RuleExtractorHelperTest, TestGetGapsWithExtensions) {
+  helper = make_shared<RuleExtractorHelper>(source_data_array,
+      target_data_array, alignment, 10, 5, true, true, true);
+  EXPECT_CALL(*source_data_array, GetSentenceLength(_))
+      .WillRepeatedly(Return(7));
+  EXPECT_CALL(*target_data_array, GetSentenceLength(_))
+      .WillRepeatedly(Return(7));
+
+  bool met_constraints = true;
+  vector<int> source_low = {-1, 5, 2, 3, 4, 1, -1};
+  vector<int> source_high = {-1, 6, 3, 4, 5, 2, -1};
+  vector<int> target_low = {-1, 5, 2, 3, 4, 1, -1};
+  vector<int> target_high = {-1, 6, 3, 4, 5, 2, -1};
+  int source_phrase_low = 2, source_phrase_high = 5;
+  int source_back_low = 1, source_back_high = 6;
+  vector<int> matching = {12, 14};
+  vector<int> chunklen = {1, 1};
+  vector<pair<int, int> > source_gaps, target_gaps;
+  int num_symbols = 3;
+  EXPECT_TRUE(helper->GetGaps(source_gaps, target_gaps, matching, chunklen,
+                              source_low, source_high, target_low, target_high,
+                              source_phrase_low, source_phrase_high,
+                              source_back_low, source_back_high, 5, 10,
+                              num_symbols, met_constraints));
+  vector<pair<int, int> > expected_source_gaps = {
+    make_pair(1, 2), make_pair(3, 4), make_pair(5, 6)
+  };
+  EXPECT_EQ(expected_source_gaps, source_gaps);
+  vector<pair<int, int> > expected_target_gaps = {
+    make_pair(5, 6), make_pair(3, 4), make_pair(1, 2)
+  };
+  EXPECT_EQ(expected_target_gaps, target_gaps);
+}
+
+TEST_F(RuleExtractorHelperTest, TestGetGaps) {
+  helper = make_shared<RuleExtractorHelper>(source_data_array,
+      target_data_array, alignment, 10, 5, true, true, true);
+  EXPECT_CALL(*source_data_array, GetSentenceLength(_))
+      .WillRepeatedly(Return(7));
+  EXPECT_CALL(*target_data_array, GetSentenceLength(_))
+      .WillRepeatedly(Return(7));
+
+  bool met_constraints = true;
+  vector<int> source_low = {-1, 1, 4, 3, 2, 5, -1};
+  vector<int> source_high = {-1, 2, 5, 4, 3, 6, -1};
+  vector<int> target_low = {-1, 1, 4, 3, 2, 5, -1};
+  vector<int> target_high = {-1, 2, 5, 4, 3, 6, -1};
+  int source_phrase_low = 1, source_phrase_high = 6;
+  int source_back_low = 1, source_back_high = 6;
+  vector<int> matching = {11, 13, 15};
+  vector<int> chunklen = {1, 1, 1};
+  vector<pair<int, int> > source_gaps, target_gaps;
+  int num_symbols = 5;
+  EXPECT_TRUE(helper->GetGaps(source_gaps, target_gaps, matching, chunklen,
+                              source_low, source_high, target_low, target_high,
+                              source_phrase_low, source_phrase_high,
+                              source_back_low, source_back_high, 5, 10,
+                              num_symbols, met_constraints));
+  vector<pair<int, int> > expected_source_gaps = {
+    make_pair(2, 3), make_pair(4, 5)
+  };
+  EXPECT_EQ(expected_source_gaps, source_gaps);
+  vector<pair<int, int> > expected_target_gaps = {
+    make_pair(4, 5), make_pair(2, 3)
+  };
+  EXPECT_EQ(expected_target_gaps, target_gaps);
+}
+
+TEST_F(RuleExtractorHelperTest, TestGetGapIntegrityChecksFailed) {
+  helper = make_shared<RuleExtractorHelper>(source_data_array,
+      target_data_array, alignment, 10, 5, true, true, true);
+  EXPECT_CALL(*source_data_array, GetSentenceLength(_))
+      .WillRepeatedly(Return(7));
+  EXPECT_CALL(*target_data_array, GetSentenceLength(_))
+      .WillRepeatedly(Return(7));
+
+  bool met_constraints = true;
+  vector<int> source_low = {-1, 3, 2, 3, 4, 3, -1};
+  vector<int> source_high = {-1, 4, 3, 4, 5, 4, -1};
+  vector<int> target_low = {-1, -1, 2, 1, 4, -1, -1};
+  vector<int> target_high = {-1, -1, 3, 6, 5, -1, -1};
+  int source_phrase_low = 2, source_phrase_high = 5;
+  int source_back_low = 2, source_back_high = 5;
+  vector<int> matching = {12, 14};
+  vector<int> chunklen = {1, 1};
+  vector<pair<int, int> > source_gaps, target_gaps;
+  int num_symbols = 3;
+  EXPECT_FALSE(helper->GetGaps(source_gaps, target_gaps, matching, chunklen,
+                               source_low, source_high, target_low, target_high,
+                               source_phrase_low, source_phrase_high,
+                               source_back_low, source_back_high, 5, 10,
+                               num_symbols, met_constraints));
+}
+
+TEST_F(RuleExtractorHelperTest, TestGetSourceIndexes) {
+  helper = make_shared<RuleExtractorHelper>(source_data_array,
+      target_data_array, alignment, 10, 5, true, true, true);
+
+  vector<int> matching = {13, 18, 21};
+  vector<int> chunklen = {3, 2, 1};
+  unordered_map<int, int> expected_indexes = {
+      {3, 1}, {4, 2}, {5, 3}, {8, 5}, {9, 6}, {11, 8}
+  };
+  EXPECT_EQ(expected_indexes, helper->GetSourceIndexes(matching, chunklen,
+                                                       1, 10));
+
+  matching = {12, 17};
+  chunklen = {2, 4};
+  expected_indexes = {{2, 0}, {3, 1}, {7, 3}, {8, 4}, {9, 5}, {10, 6}};
+  EXPECT_EQ(expected_indexes, helper->GetSourceIndexes(matching, chunklen,
+                                                       0, 10));
+}
+
+} // namespace
+} // namespace extractor
diff --git a/extractor/rule_extractor_test.cc b/extractor/rule_extractor_test.cc
new file mode 100644
index 00000000..5c1501c7
--- /dev/null
+++ b/extractor/rule_extractor_test.cc
@@ -0,0 +1,168 @@
+#include <gtest/gtest.h>
+
+#include <memory>
+
+#include "mocks/mock_alignment.h"
+#include "mocks/mock_data_array.h"
+#include "mocks/mock_rule_extractor_helper.h"
+#include "mocks/mock_scorer.h"
+#include "mocks/mock_target_phrase_extractor.h"
+#include "mocks/mock_vocabulary.h"
+#include "phrase.h"
+#include "phrase_builder.h"
+#include "phrase_location.h"
+#include "rule_extractor.h"
+#include "rule.h"
+
+using namespace std;
+using namespace ::testing;
+
+namespace extractor {
+namespace {
+
+class RuleExtractorTest : public Test {
+ protected:
+  virtual void SetUp() {
+    source_data_array = make_shared<MockDataArray>();
+    EXPECT_CALL(*source_data_array, GetSentenceId(_))
+        .WillRepeatedly(Return(0));
+    EXPECT_CALL(*source_data_array, GetSentenceStart(_))
+        .WillRepeatedly(Return(0));
+    EXPECT_CALL(*source_data_array, GetSentenceLength(_))
+        .WillRepeatedly(Return(10));
+
+    helper = make_shared<MockRuleExtractorHelper>();
+    EXPECT_CALL(*helper, CheckAlignedTerminals(_, _, _, _))
+        .WillRepeatedly(Return(true));
+    EXPECT_CALL(*helper, CheckTightPhrases(_, _, _, _))
+        .WillRepeatedly(Return(true));
+    unordered_map<int, int> source_indexes;
+    EXPECT_CALL(*helper, GetSourceIndexes(_, _, _, _))
+        .WillRepeatedly(Return(source_indexes));
+
+    vocabulary = make_shared<MockVocabulary>();
+    EXPECT_CALL(*vocabulary, GetTerminalValue(87))
+        .WillRepeatedly(Return("a"));
+    phrase_builder = make_shared<PhraseBuilder>(vocabulary);
+    vector<int> symbols = {87};
+    Phrase target_phrase = phrase_builder->Build(symbols);
+    PhraseAlignment phrase_alignment = {make_pair(0, 0)};
+
+    target_phrase_extractor = make_shared<MockTargetPhraseExtractor>();
+    vector<pair<Phrase, PhraseAlignment> > target_phrases = {
+      make_pair(target_phrase, phrase_alignment)
+    };
+    EXPECT_CALL(*target_phrase_extractor, ExtractPhrases(_, _, _, _, _, _))
+        .WillRepeatedly(Return(target_phrases));
+
+    scorer = make_shared<MockScorer>();
+    vector<double> scores = {0.3, 7.2};
+    EXPECT_CALL(*scorer, Score(_)).WillRepeatedly(Return(scores));
+
+    extractor = make_shared<RuleExtractor>(source_data_array, phrase_builder,
+        scorer, target_phrase_extractor, helper, 10, 1, 3, 5, false);
+  }
+
+  shared_ptr<MockDataArray> source_data_array;
+  shared_ptr<MockVocabulary> vocabulary;
+  shared_ptr<PhraseBuilder> phrase_builder;
+  shared_ptr<MockRuleExtractorHelper> helper;
+  shared_ptr<MockScorer> scorer;
+  shared_ptr<MockTargetPhraseExtractor> target_phrase_extractor;
+  shared_ptr<RuleExtractor> extractor;
+};
+
+TEST_F(RuleExtractorTest, TestExtractRulesAlignedTerminalsFail) {
+  vector<int> symbols = {87};
+  Phrase phrase = phrase_builder->Build(symbols);
+  vector<int> matching = {2};
+  PhraseLocation phrase_location(matching, 1);
+  EXPECT_CALL(*helper, GetLinksSpans(_, _, _, _, _)).Times(1);
+  EXPECT_CALL(*helper, CheckAlignedTerminals(_, _, _, _))
+      .WillRepeatedly(Return(false));
+  vector<Rule> rules = extractor->ExtractRules(phrase, phrase_location);
+  EXPECT_EQ(0, rules.size());
+}
+
+TEST_F(RuleExtractorTest, TestExtractRulesTightPhrasesFail) {
+  vector<int> symbols = {87};
+  Phrase phrase = phrase_builder->Build(symbols);
+  vector<int> matching = {2};
+  PhraseLocation phrase_location(matching, 1);
+  EXPECT_CALL(*helper, GetLinksSpans(_, _, _, _, _)).Times(1);
+  EXPECT_CALL(*helper, CheckTightPhrases(_, _, _, _))
+      .WillRepeatedly(Return(false));
+  vector<Rule> rules = extractor->ExtractRules(phrase, phrase_location);
+  EXPECT_EQ(0, rules.size());
+}
+
+TEST_F(RuleExtractorTest, TestExtractRulesNoFixPoint) {
+  vector<int> symbols = {87};
+  Phrase phrase = phrase_builder->Build(symbols);
+  vector<int> matching = {2};
+  PhraseLocation phrase_location(matching, 1);
+
+  EXPECT_CALL(*helper, GetLinksSpans(_, _, _, _, _)).Times(1);
+  // Set FindFixPoint to return false.
+  vector<pair<int, int> > gaps;
+  helper->SetUp(0, 0, 0, 0, false, gaps, gaps, 0, true, true);
+
+  vector<Rule> rules = extractor->ExtractRules(phrase, phrase_location);
+  EXPECT_EQ(0, rules.size());
+}
+
+TEST_F(RuleExtractorTest, TestExtractRulesGapsFail) {
+  vector<int> symbols = {87};
+  Phrase phrase = phrase_builder->Build(symbols);
+  vector<int> matching = {2};
+  PhraseLocation phrase_location(matching, 1);
+
+  EXPECT_CALL(*helper, GetLinksSpans(_, _, _, _, _)).Times(1);
+  // Set CheckGaps to return false.
+  vector<pair<int, int> > gaps;
+  helper->SetUp(0, 0, 0, 0, true, gaps, gaps, 0, true, false);
+
+  vector<Rule> rules = extractor->ExtractRules(phrase, phrase_location);
+  EXPECT_EQ(0, rules.size());
+}
+
+TEST_F(RuleExtractorTest, TestExtractRulesNoExtremities) {
+  vector<int> symbols = {87};
+  Phrase phrase = phrase_builder->Build(symbols);
+  vector<int> matching = {2};
+  PhraseLocation phrase_location(matching, 1);
+
+  EXPECT_CALL(*helper, GetLinksSpans(_, _, _, _, _)).Times(1);
+  vector<pair<int, int> > gaps(3);
+  // Set FindFixPoint to return true. The number of gaps equals the number of
+  // nonterminals, so we won't add any extremities.
+  helper->SetUp(0, 0, 0, 0, true, gaps, gaps, 0, true, true);
+
+  vector<Rule> rules = extractor->ExtractRules(phrase, phrase_location);
+  EXPECT_EQ(1, rules.size());
+}
+
+TEST_F(RuleExtractorTest, TestExtractRulesAddExtremities) {
+  vector<int> symbols = {87};
+  Phrase phrase = phrase_builder->Build(symbols);
+  vector<int> matching = {2};
+  PhraseLocation phrase_location(matching, 1);
+
+  vector<int> links(10, -1);
+  EXPECT_CALL(*helper, GetLinksSpans(_, _, _, _, _)).WillOnce(DoAll(
+      SetArgReferee<0>(links),
+      SetArgReferee<1>(links),
+      SetArgReferee<2>(links),
+      SetArgReferee<3>(links)));
+
+  vector<pair<int, int> > gaps;
+  // Set FindFixPoint to return true. The number of gaps equals the number of
+  // nonterminals, so we won't add any extremities.
+  helper->SetUp(0, 0, 2, 3, true, gaps, gaps, 0, true, true);
+
+  vector<Rule> rules = extractor->ExtractRules(phrase, phrase_location);
+  EXPECT_EQ(4, rules.size());
+}
+
+} // namespace
+} // namespace extractor
diff --git a/extractor/rule_factory.cc b/extractor/rule_factory.cc
new file mode 100644
index 00000000..8c30fb9e
--- /dev/null
+++ b/extractor/rule_factory.cc
@@ -0,0 +1,303 @@
+#include "rule_factory.h"
+
+#include <chrono>
+#include <memory>
+#include <queue>
+#include <vector>
+
+#include "grammar.h"
+#include "fast_intersector.h"
+#include "matchings_finder.h"
+#include "phrase.h"
+#include "phrase_builder.h"
+#include "rule.h"
+#include "rule_extractor.h"
+#include "sampler.h"
+#include "scorer.h"
+#include "suffix_array.h"
+#include "time_util.h"
+#include "vocabulary.h"
+
+using namespace std;
+using namespace chrono;
+
+namespace extractor {
+
+typedef high_resolution_clock Clock;
+
+struct State {
+  State(int start, int end, const vector<int>& phrase,
+      const vector<int>& subpatterns_start, shared_ptr<TrieNode> node,
+      bool starts_with_x) :
+      start(start), end(end), phrase(phrase),
+      subpatterns_start(subpatterns_start), node(node),
+      starts_with_x(starts_with_x) {}
+
+  int start, end;
+  vector<int> phrase, subpatterns_start;
+  shared_ptr<TrieNode> node;
+  bool starts_with_x;
+};
+
+HieroCachingRuleFactory::HieroCachingRuleFactory(
+    shared_ptr<SuffixArray> source_suffix_array,
+    shared_ptr<DataArray> target_data_array,
+    shared_ptr<Alignment> alignment,
+    const shared_ptr<Vocabulary>& vocabulary,
+    shared_ptr<Precomputation> precomputation,
+    shared_ptr<Scorer> scorer,
+    int min_gap_size,
+    int max_rule_span,
+    int max_nonterminals,
+    int max_rule_symbols,
+    int max_samples,
+    bool require_tight_phrases) :
+    vocabulary(vocabulary),
+    scorer(scorer),
+    min_gap_size(min_gap_size),
+    max_rule_span(max_rule_span),
+    max_nonterminals(max_nonterminals),
+    max_chunks(max_nonterminals + 1),
+    max_rule_symbols(max_rule_symbols) {
+  matchings_finder = make_shared<MatchingsFinder>(source_suffix_array);
+  fast_intersector = make_shared<FastIntersector>(source_suffix_array,
+      precomputation, vocabulary, max_rule_span, min_gap_size);
+  phrase_builder = make_shared<PhraseBuilder>(vocabulary);
+  rule_extractor = make_shared<RuleExtractor>(source_suffix_array->GetData(),
+      target_data_array, alignment, phrase_builder, scorer, vocabulary,
+      max_rule_span, min_gap_size, max_nonterminals, max_rule_symbols, true,
+      false, require_tight_phrases);
+  sampler = make_shared<Sampler>(source_suffix_array, max_samples);
+}
+
+HieroCachingRuleFactory::HieroCachingRuleFactory(
+    shared_ptr<MatchingsFinder> finder,
+    shared_ptr<FastIntersector> fast_intersector,
+    shared_ptr<PhraseBuilder> phrase_builder,
+    shared_ptr<RuleExtractor> rule_extractor,
+    shared_ptr<Vocabulary> vocabulary,
+    shared_ptr<Sampler> sampler,
+    shared_ptr<Scorer> scorer,
+    int min_gap_size,
+    int max_rule_span,
+    int max_nonterminals,
+    int max_chunks,
+    int max_rule_symbols) :
+    matchings_finder(finder),
+    fast_intersector(fast_intersector),
+    phrase_builder(phrase_builder),
+    rule_extractor(rule_extractor),
+    vocabulary(vocabulary),
+    sampler(sampler),
+    scorer(scorer),
+    min_gap_size(min_gap_size),
+    max_rule_span(max_rule_span),
+    max_nonterminals(max_nonterminals),
+    max_chunks(max_chunks),
+    max_rule_symbols(max_rule_symbols) {}
+
+HieroCachingRuleFactory::HieroCachingRuleFactory() {}
+
+HieroCachingRuleFactory::~HieroCachingRuleFactory() {}
+
+Grammar HieroCachingRuleFactory::GetGrammar(const vector<int>& word_ids) {
+  Clock::time_point start_time = Clock::now();
+  double total_extract_time = 0;
+  double total_intersect_time = 0;
+  double total_lookup_time = 0;
+
+  MatchingsTrie trie;
+  shared_ptr<TrieNode> root = trie.GetRoot();
+
+  int first_x = vocabulary->GetNonterminalIndex(1);
+  shared_ptr<TrieNode> x_root(new TrieNode(root));
+  root->AddChild(first_x, x_root);
+
+  queue<State> states;
+  for (size_t i = 0; i < word_ids.size(); ++i) {
+    states.push(State(i, i, vector<int>(), vector<int>(1, i), root, false));
+  }
+  for (size_t i = min_gap_size; i < word_ids.size(); ++i) {
+    states.push(State(i - min_gap_size, i, vector<int>(1, first_x),
+        vector<int>(1, i), x_root, true));
+  }
+
+  vector<Rule> rules;
+  while (!states.empty()) {
+    State state = states.front();
+    states.pop();
+
+    shared_ptr<TrieNode> node = state.node;
+    vector<int> phrase = state.phrase;
+    int word_id = word_ids[state.end];
+    phrase.push_back(word_id);
+    Phrase next_phrase = phrase_builder->Build(phrase);
+    shared_ptr<TrieNode> next_node;
+
+    if (CannotHaveMatchings(node, word_id)) {
+      if (!node->HasChild(word_id)) {
+        node->AddChild(word_id, shared_ptr<TrieNode>());
+      }
+      continue;
+    }
+
+    if (RequiresLookup(node, word_id)) {
+      shared_ptr<TrieNode> next_suffix_link = node->suffix_link == NULL ?
+          trie.GetRoot() : node->suffix_link->GetChild(word_id);
+      if (state.starts_with_x) {
+        // If the phrase starts with a non terminal, we simply use the matchings
+        // from the suffix link.
+        next_node = make_shared<TrieNode>(
+            next_suffix_link, next_phrase, next_suffix_link->matchings);
+      } else {
+        PhraseLocation phrase_location;
+        if (next_phrase.Arity() > 0) {
+          // For phrases containing a nonterminal, we use either the occurrences
+          // of the prefix or the suffix to determine the occurrences of the
+          // phrase.
+          Clock::time_point intersect_start = Clock::now();
+          phrase_location = fast_intersector->Intersect(
+              node->matchings, next_suffix_link->matchings, next_phrase);
+          Clock::time_point intersect_stop = Clock::now();
+          total_intersect_time += GetDuration(intersect_start, intersect_stop);
+        } else {
+          // For phrases not containing any nonterminals, we simply query the
+          // suffix array using the suffix array range of the prefix as a
+          // starting point.
+          Clock::time_point lookup_start = Clock::now();
+          phrase_location = matchings_finder->Find(
+              node->matchings,
+              vocabulary->GetTerminalValue(word_id),
+              state.phrase.size());
+          Clock::time_point lookup_stop = Clock::now();
+          total_lookup_time += GetDuration(lookup_start, lookup_stop);
+        }
+
+        if (phrase_location.IsEmpty()) {
+          continue;
+        }
+
+        // Create new trie node to store data about the current phrase.
+        next_node = make_shared<TrieNode>(
+            next_suffix_link, next_phrase, phrase_location);
+      }
+      // Add the new trie node to the trie cache.
+      node->AddChild(word_id, next_node);
+
+      // Automatically adds a trailing non terminal if allowed. Simply copy the
+      // matchings from the prefix node.
+      AddTrailingNonterminal(phrase, next_phrase, next_node,
+                             state.starts_with_x);
+
+      Clock::time_point extract_start = Clock::now();
+      if (!state.starts_with_x) {
+        // Extract rules for the sampled set of occurrences.
+        PhraseLocation sample = sampler->Sample(next_node->matchings);
+        vector<Rule> new_rules =
+            rule_extractor->ExtractRules(next_phrase, sample);
+        rules.insert(rules.end(), new_rules.begin(), new_rules.end());
+      }
+      Clock::time_point extract_stop = Clock::now();
+      total_extract_time += GetDuration(extract_start, extract_stop);
+    } else {
+      next_node = node->GetChild(word_id);
+    }
+
+    // Create more states (phrases) to be analyzed.
+    vector<State> new_states = ExtendState(word_ids, state, phrase, next_phrase,
+                                           next_node);
+    for (State new_state: new_states) {
+      states.push(new_state);
+    }
+  }
+
+  Clock::time_point stop_time = Clock::now();
+  #pragma omp critical (stderr_write)
+  {
+    cerr << "Total time for rule lookup, extraction, and scoring = "
+         << GetDuration(start_time, stop_time) << " seconds" << endl;
+    cerr << "Extract time = " << total_extract_time << " seconds" << endl;
+    cerr << "Intersect time = " << total_intersect_time << " seconds" << endl;
+    cerr << "Lookup time = " << total_lookup_time << " seconds" << endl;
+  }
+  return Grammar(rules, scorer->GetFeatureNames());
+}
+
+bool HieroCachingRuleFactory::CannotHaveMatchings(
+    shared_ptr<TrieNode> node, int word_id) {
+  if (node->HasChild(word_id) && node->GetChild(word_id) == NULL) {
+    return true;
+  }
+
+  shared_ptr<TrieNode> suffix_link = node->suffix_link;
+  return suffix_link != NULL && suffix_link->GetChild(word_id) == NULL;
+}
+
+bool HieroCachingRuleFactory::RequiresLookup(
+    shared_ptr<TrieNode> node, int word_id) {
+  return !node->HasChild(word_id);
+}
+
+void HieroCachingRuleFactory::AddTrailingNonterminal(
+    vector<int> symbols,
+    const Phrase& prefix,
+    const shared_ptr<TrieNode>& prefix_node,
+    bool starts_with_x) {
+  if (prefix.Arity() >= max_nonterminals) {
+    return;
+  }
+
+  int var_id = vocabulary->GetNonterminalIndex(prefix.Arity() + 1);
+  symbols.push_back(var_id);
+  Phrase var_phrase = phrase_builder->Build(symbols);
+
+  int suffix_var_id = vocabulary->GetNonterminalIndex(
+      prefix.Arity() + (starts_with_x == 0));
+  shared_ptr<TrieNode> var_suffix_link =
+      prefix_node->suffix_link->GetChild(suffix_var_id);
+
+  prefix_node->AddChild(var_id, make_shared<TrieNode>(
+      var_suffix_link, var_phrase, prefix_node->matchings));
+}
+
+vector<State> HieroCachingRuleFactory::ExtendState(
+    const vector<int>& word_ids,
+    const State& state,
+    vector<int> symbols,
+    const Phrase& phrase,
+    const shared_ptr<TrieNode>& node) {
+  int span = state.end - state.start;
+  vector<State> new_states;
+  if (symbols.size() >= max_rule_symbols || state.end + 1 >= word_ids.size() ||
+      span >= max_rule_span) {
+    return new_states;
+  }
+
+  // New state for adding the next symbol.
+  new_states.push_back(State(state.start, state.end + 1, symbols,
+      state.subpatterns_start, node, state.starts_with_x));
+
+  int num_subpatterns = phrase.Arity() + (state.starts_with_x == 0);
+  if (symbols.size() + 1 >= max_rule_symbols ||
+      phrase.Arity() >= max_nonterminals ||
+      num_subpatterns >= max_chunks) {
+    return new_states;
+  }
+
+  // New states for adding a nonterminal followed by a new symbol.
+  int var_id = vocabulary->GetNonterminalIndex(phrase.Arity() + 1);
+  symbols.push_back(var_id);
+  vector<int> subpatterns_start = state.subpatterns_start;
+  size_t i = state.end + 1 + min_gap_size;
+  while (i < word_ids.size() && i - state.start <= max_rule_span) {
+    subpatterns_start.push_back(i);
+    new_states.push_back(State(state.start, i, symbols, subpatterns_start,
+        node->GetChild(var_id), state.starts_with_x));
+    subpatterns_start.pop_back();
+    ++i;
+  }
+
+  return new_states;
+}
+
+} // namespace extractor
diff --git a/extractor/rule_factory.h b/extractor/rule_factory.h
new file mode 100644
index 00000000..52e8712a
--- /dev/null
+++ b/extractor/rule_factory.h
@@ -0,0 +1,118 @@
+#ifndef _RULE_FACTORY_H_
+#define _RULE_FACTORY_H_
+
+#include <memory>
+#include <vector>
+
+#include "matchings_trie.h"
+
+using namespace std;
+
+namespace extractor {
+
+class Alignment;
+class DataArray;
+class FastIntersector;
+class Grammar;
+class MatchingsFinder;
+class PhraseBuilder;
+class Precomputation;
+class Rule;
+class RuleExtractor;
+class Sampler;
+class Scorer;
+class State;
+class SuffixArray;
+class Vocabulary;
+
+/**
+ * Component containing most of the logic for extracting SCFG rules for a given
+ * sentence.
+ *
+ * Given a sentence (as a vector of word ids), this class constructs all the
+ * possible source phrases starting from this sentence. For each source phrase,
+ * it finds all its occurrences in the source data and samples some of these
+ * occurrences to extract aligned source-target phrase pairs. A trie cache is
+ * used to avoid unnecessary computations if a source phrase can be constructed
+ * more than once (e.g. some words occur more than once in the sentence).
+ */
+class HieroCachingRuleFactory {
+ public:
+  HieroCachingRuleFactory(
+      shared_ptr<SuffixArray> source_suffix_array,
+      shared_ptr<DataArray> target_data_array,
+      shared_ptr<Alignment> alignment,
+      const shared_ptr<Vocabulary>& vocabulary,
+      shared_ptr<Precomputation> precomputation,
+      shared_ptr<Scorer> scorer,
+      int min_gap_size,
+      int max_rule_span,
+      int max_nonterminals,
+      int max_rule_symbols,
+      int max_samples,
+      bool require_tight_phrases);
+
+  // For testing only.
+  HieroCachingRuleFactory(
+      shared_ptr<MatchingsFinder> finder,
+      shared_ptr<FastIntersector> fast_intersector,
+      shared_ptr<PhraseBuilder> phrase_builder,
+      shared_ptr<RuleExtractor> rule_extractor,
+      shared_ptr<Vocabulary> vocabulary,
+      shared_ptr<Sampler> sampler,
+      shared_ptr<Scorer> scorer,
+      int min_gap_size,
+      int max_rule_span,
+      int max_nonterminals,
+      int max_chunks,
+      int max_rule_symbols);
+
+  virtual ~HieroCachingRuleFactory();
+
+  // Constructs SCFG rules for a given sentence.
+  // (See class description for more details.)
+  virtual Grammar GetGrammar(const vector<int>& word_ids);
+
+ protected:
+  HieroCachingRuleFactory();
+
+ private:
+  // Checks if the phrase (if previously encountered) or its prefix have any
+  // occurrences in the source data.
+  bool CannotHaveMatchings(shared_ptr<TrieNode> node, int word_id);
+
+  // Checks if the phrase has previously been analyzed.
+  bool RequiresLookup(shared_ptr<TrieNode> node, int word_id);
+
+  // Creates a new state in the trie that corresponds to adding a trailing
+  // nonterminal to the current phrase.
+  void AddTrailingNonterminal(vector<int> symbols,
+                              const Phrase& prefix,
+                              const shared_ptr<TrieNode>& prefix_node,
+                              bool starts_with_x);
+
+  // Extends the current state by possibly adding a nonterminal followed by a
+  // terminal.
+  vector<State> ExtendState(const vector<int>& word_ids,
+                            const State& state,
+                            vector<int> symbols,
+                            const Phrase& phrase,
+                            const shared_ptr<TrieNode>& node);
+
+  shared_ptr<MatchingsFinder> matchings_finder;
+  shared_ptr<FastIntersector> fast_intersector;
+  shared_ptr<PhraseBuilder> phrase_builder;
+  shared_ptr<RuleExtractor> rule_extractor;
+  shared_ptr<Vocabulary> vocabulary;
+  shared_ptr<Sampler> sampler;
+  shared_ptr<Scorer> scorer;
+  int min_gap_size;
+  int max_rule_span;
+  int max_nonterminals;
+  int max_chunks;
+  int max_rule_symbols;
+};
+
+} // namespace extractor
+
+#endif
diff --git a/extractor/rule_factory_test.cc b/extractor/rule_factory_test.cc
new file mode 100644
index 00000000..2129dfa0
--- /dev/null
+++ b/extractor/rule_factory_test.cc
@@ -0,0 +1,103 @@
+#include <gtest/gtest.h>
+
+#include <memory>
+#include <string>
+#include <vector>
+
+#include "grammar.h"
+#include "mocks/mock_fast_intersector.h"
+#include "mocks/mock_matchings_finder.h"
+#include "mocks/mock_rule_extractor.h"
+#include "mocks/mock_sampler.h"
+#include "mocks/mock_scorer.h"
+#include "mocks/mock_vocabulary.h"
+#include "phrase_builder.h"
+#include "phrase_location.h"
+#include "rule_factory.h"
+
+using namespace std;
+using namespace ::testing;
+
+namespace extractor {
+namespace {
+
+class RuleFactoryTest : public Test {
+ protected:
+  virtual void SetUp() {
+    finder = make_shared<MockMatchingsFinder>();
+    fast_intersector = make_shared<MockFastIntersector>();
+
+    vocabulary = make_shared<MockVocabulary>();
+    EXPECT_CALL(*vocabulary, GetTerminalValue(2)).WillRepeatedly(Return("a"));
+    EXPECT_CALL(*vocabulary, GetTerminalValue(3)).WillRepeatedly(Return("b"));
+    EXPECT_CALL(*vocabulary, GetTerminalValue(4)).WillRepeatedly(Return("c"));
+
+    phrase_builder = make_shared<PhraseBuilder>(vocabulary);
+
+    scorer = make_shared<MockScorer>();
+    feature_names = {"f1"};
+    EXPECT_CALL(*scorer, GetFeatureNames())
+        .WillRepeatedly(Return(feature_names));
+
+    sampler = make_shared<MockSampler>();
+    EXPECT_CALL(*sampler, Sample(_))
+        .WillRepeatedly(Return(PhraseLocation(0, 1)));
+
+    Phrase phrase;
+    vector<double> scores = {0.5};
+    vector<pair<int, int> > phrase_alignment = {make_pair(0, 0)};
+    vector<Rule> rules = {Rule(phrase, phrase, scores, phrase_alignment)};
+    extractor = make_shared<MockRuleExtractor>();
+    EXPECT_CALL(*extractor, ExtractRules(_, _))
+        .WillRepeatedly(Return(rules));
+  }
+
+  vector<string> feature_names;
+  shared_ptr<MockMatchingsFinder> finder;
+  shared_ptr<MockFastIntersector> fast_intersector;
+  shared_ptr<MockVocabulary> vocabulary;
+  shared_ptr<PhraseBuilder> phrase_builder;
+  shared_ptr<MockScorer> scorer;
+  shared_ptr<MockSampler> sampler;
+  shared_ptr<MockRuleExtractor> extractor;
+  shared_ptr<HieroCachingRuleFactory> factory;
+};
+
+TEST_F(RuleFactoryTest, TestGetGrammarDifferentWords) {
+  factory = make_shared<HieroCachingRuleFactory>(finder, fast_intersector,
+      phrase_builder, extractor, vocabulary, sampler, scorer, 1, 10, 2, 3, 5);
+
+  EXPECT_CALL(*finder, Find(_, _, _))
+      .Times(6)
+      .WillRepeatedly(Return(PhraseLocation(0, 1)));
+
+  EXPECT_CALL(*fast_intersector, Intersect(_, _, _))
+      .Times(1)
+      .WillRepeatedly(Return(PhraseLocation(0, 1)));
+
+  vector<int> word_ids = {2, 3, 4};
+  Grammar grammar = factory->GetGrammar(word_ids);
+  EXPECT_EQ(feature_names, grammar.GetFeatureNames());
+  EXPECT_EQ(7, grammar.GetRules().size());
+}
+
+TEST_F(RuleFactoryTest, TestGetGrammarRepeatingWords) {
+  factory = make_shared<HieroCachingRuleFactory>(finder, fast_intersector,
+      phrase_builder, extractor, vocabulary, sampler, scorer, 1, 10, 2, 3, 5);
+
+  EXPECT_CALL(*finder, Find(_, _, _))
+      .Times(12)
+      .WillRepeatedly(Return(PhraseLocation(0, 1)));
+
+  EXPECT_CALL(*fast_intersector, Intersect(_, _, _))
+      .Times(16)
+      .WillRepeatedly(Return(PhraseLocation(0, 1)));
+
+  vector<int> word_ids = {2, 3, 4, 2, 3};
+  Grammar grammar = factory->GetGrammar(word_ids);
+  EXPECT_EQ(feature_names, grammar.GetFeatureNames());
+  EXPECT_EQ(28, grammar.GetRules().size());
+}
+
+} // namespace
+} // namespace extractor
diff --git a/extractor/run_extractor.cc b/extractor/run_extractor.cc
new file mode 100644
index 00000000..aec83e3b
--- /dev/null
+++ b/extractor/run_extractor.cc
@@ -0,0 +1,242 @@
+#include <chrono>
+#include <fstream>
+#include <iostream>
+#include <memory>
+#include <string>
+#include <vector>
+
+#include <omp.h>
+#include <boost/filesystem.hpp>
+#include <boost/program_options.hpp>
+#include <boost/program_options/variables_map.hpp>
+
+#include "alignment.h"
+#include "data_array.h"
+#include "features/count_source_target.h"
+#include "features/feature.h"
+#include "features/is_source_singleton.h"
+#include "features/is_source_target_singleton.h"
+#include "features/max_lex_source_given_target.h"
+#include "features/max_lex_target_given_source.h"
+#include "features/sample_source_count.h"
+#include "features/target_given_source_coherent.h"
+#include "grammar.h"
+#include "grammar_extractor.h"
+#include "precomputation.h"
+#include "rule.h"
+#include "scorer.h"
+#include "suffix_array.h"
+#include "time_util.h"
+#include "translation_table.h"
+
+namespace fs = boost::filesystem;
+namespace po = boost::program_options;
+using namespace std;
+using namespace extractor;
+using namespace features;
+
+// Returns the file path in which a given grammar should be written.
+fs::path GetGrammarFilePath(const fs::path& grammar_path, int file_number) {
+  string file_name = "grammar." + to_string(file_number);
+  return grammar_path / file_name;
+}
+
+int main(int argc, char** argv) {
+  int num_threads_default = 1;
+  #pragma omp parallel
+  num_threads_default = omp_get_num_threads();
+
+  // Sets up the command line arguments map.
+  po::options_description desc("Command line options");
+  desc.add_options()
+    ("help,h", "Show available options")
+    ("source,f", po::value<string>(), "Source language corpus")
+    ("target,e", po::value<string>(), "Target language corpus")
+    ("bitext,b", po::value<string>(), "Parallel text (source ||| target)")
+    ("alignment,a", po::value<string>()->required(), "Bitext word alignment")
+    ("grammars,g", po::value<string>()->required(), "Grammars output path")
+    ("threads,t", po::value<int>()->default_value(num_threads_default),
+        "Number of parallel extractors")
+    ("frequent", po::value<int>()->default_value(100),
+        "Number of precomputed frequent patterns")
+    ("super_frequent", po::value<int>()->default_value(10),
+        "Number of precomputed super frequent patterns")
+    ("max_rule_span", po::value<int>()->default_value(15),
+        "Maximum rule span")
+    ("max_rule_symbols", po::value<int>()->default_value(5),
+        "Maximum number of symbols (terminals + nontermals) in a rule")
+    ("min_gap_size", po::value<int>()->default_value(1), "Minimum gap size")
+    ("max_phrase_len", po::value<int>()->default_value(4),
+        "Maximum frequent phrase length")
+    ("max_nonterminals", po::value<int>()->default_value(2),
+        "Maximum number of nonterminals in a rule")
+    ("min_frequency", po::value<int>()->default_value(1000),
+        "Minimum number of occurrences for a pharse to be considered frequent")
+    ("max_samples", po::value<int>()->default_value(300),
+        "Maximum number of samples")
+    ("tight_phrases", po::value<bool>()->default_value(true),
+        "False if phrases may be loose (better, but slower)");
+
+  po::variables_map vm;
+  po::store(po::parse_command_line(argc, argv, desc), vm);
+
+  // Checks for the help option before calling notify, so the we don't get an
+  // exception for missing required arguments.
+  if (vm.count("help")) {
+    cout << desc << endl;
+    return 0;
+  }
+
+  po::notify(vm);
+
+  if (!((vm.count("source") && vm.count("target")) || vm.count("bitext"))) {
+    cerr << "A paralel corpus is required. "
+         << "Use -f (source) with -e (target) or -b (bitext)."
+         << endl;
+    return 1;
+  }
+
+  int num_threads = vm["threads"].as<int>();
+  cout << "Grammar extraction will use " << num_threads << " threads." << endl;
+
+  // Reads the parallel corpus.
+  Clock::time_point preprocess_start_time = Clock::now();
+  cerr << "Reading source and target data..." << endl;
+  Clock::time_point start_time = Clock::now();
+  shared_ptr<DataArray> source_data_array, target_data_array;
+  if (vm.count("bitext")) {
+    source_data_array = make_shared<DataArray>(
+        vm["bitext"].as<string>(), SOURCE);
+    target_data_array = make_shared<DataArray>(
+        vm["bitext"].as<string>(), TARGET);
+  } else {
+    source_data_array = make_shared<DataArray>(vm["source"].as<string>());
+    target_data_array = make_shared<DataArray>(vm["target"].as<string>());
+  }
+  Clock::time_point stop_time = Clock::now();
+  cerr << "Reading data took " << GetDuration(start_time, stop_time)
+       << " seconds" << endl;
+
+  // Constructs the suffix array for the source data.
+  cerr << "Creating source suffix array..." << endl;
+  start_time = Clock::now();
+  shared_ptr<SuffixArray> source_suffix_array =
+      make_shared<SuffixArray>(source_data_array);
+  stop_time = Clock::now();
+  cerr << "Creating suffix array took "
+       << GetDuration(start_time, stop_time) << " seconds" << endl;
+
+  // Reads the alignment.
+  cerr << "Reading alignment..." << endl;
+  start_time = Clock::now();
+  shared_ptr<Alignment> alignment =
+      make_shared<Alignment>(vm["alignment"].as<string>());
+  stop_time = Clock::now();
+  cerr << "Reading alignment took "
+       << GetDuration(start_time, stop_time) << " seconds" << endl;
+
+  // Constructs an index storing the occurrences in the source data for each
+  // frequent collocation.
+  cerr << "Precomputing collocations..." << endl;
+  start_time = Clock::now();
+  shared_ptr<Precomputation> precomputation = make_shared<Precomputation>(
+      source_suffix_array,
+      vm["frequent"].as<int>(),
+      vm["super_frequent"].as<int>(),
+      vm["max_rule_span"].as<int>(),
+      vm["max_rule_symbols"].as<int>(),
+      vm["min_gap_size"].as<int>(),
+      vm["max_phrase_len"].as<int>(),
+      vm["min_frequency"].as<int>());
+  stop_time = Clock::now();
+  cerr << "Precomputing collocations took "
+       << GetDuration(start_time, stop_time) << " seconds" << endl;
+
+  // Constructs a table storing p(e | f) and p(f | e) for every pair of source
+  // and target words.
+  cerr << "Precomputing conditional probabilities..." << endl;
+  start_time = Clock::now();
+  shared_ptr<TranslationTable> table = make_shared<TranslationTable>(
+      source_data_array, target_data_array, alignment);
+  stop_time = Clock::now();
+  cerr << "Precomputing conditional probabilities took "
+       << GetDuration(start_time, stop_time) << " seconds" << endl;
+
+  Clock::time_point preprocess_stop_time = Clock::now();
+  cerr << "Overall preprocessing step took "
+       << GetDuration(preprocess_start_time, preprocess_stop_time)
+       << " seconds" << endl;
+
+  // Features used to score each grammar rule.
+  Clock::time_point extraction_start_time = Clock::now();
+  vector<shared_ptr<Feature> > features = {
+      make_shared<TargetGivenSourceCoherent>(),
+      make_shared<SampleSourceCount>(),
+      make_shared<CountSourceTarget>(),
+      make_shared<MaxLexSourceGivenTarget>(table),
+      make_shared<MaxLexTargetGivenSource>(table),
+      make_shared<IsSourceSingleton>(),
+      make_shared<IsSourceTargetSingleton>()
+  };
+  shared_ptr<Scorer> scorer = make_shared<Scorer>(features);
+
+  // Sets up the grammar extractor.
+  GrammarExtractor extractor(
+      source_suffix_array,
+      target_data_array,
+      alignment,
+      precomputation,
+      scorer,
+      vm["min_gap_size"].as<int>(),
+      vm["max_rule_span"].as<int>(),
+      vm["max_nonterminals"].as<int>(),
+      vm["max_rule_symbols"].as<int>(),
+      vm["max_samples"].as<int>(),
+      vm["tight_phrases"].as<bool>());
+
+  // Releases extra memory used by the initial precomputation.
+  precomputation.reset();
+
+  // Creates the grammars directory if it doesn't exist.
+  fs::path grammar_path = vm["grammars"].as<string>();
+  if (!fs::is_directory(grammar_path)) {
+    fs::create_directory(grammar_path);
+  }
+
+  // Reads all sentences for which we extract grammar rules (the paralellization
+  // is simplified if we read all sentences upfront).
+  string sentence;
+  vector<string> sentences;
+  while (getline(cin, sentence)) {
+    sentences.push_back(sentence);
+  }
+
+  // Extracts the grammar for each sentence and saves it to a file.
+  vector<string> suffixes(sentences.size());
+  #pragma omp parallel for schedule(dynamic) num_threads(num_threads)
+  for (size_t i = 0; i < sentences.size(); ++i) {
+    string suffix;
+    int position = sentences[i].find("|||");
+    if (position != sentences[i].npos) {
+      suffix = sentences[i].substr(position);
+      sentences[i] = sentences[i].substr(0, position);
+    }
+    suffixes[i] = suffix;
+
+    Grammar grammar = extractor.GetGrammar(sentences[i]);
+    ofstream output(GetGrammarFilePath(grammar_path, i).c_str());
+    output << grammar;
+  }
+
+  for (size_t i = 0; i < sentences.size(); ++i) {
+    cout << "<seg grammar=\"" << GetGrammarFilePath(grammar_path, i) << "\" id=\""
+         << i << "\"> " << sentences[i] << " </seg> " << suffixes[i] << endl;
+  }
+
+  Clock::time_point extraction_stop_time = Clock::now();
+  cerr << "Overall extraction step took "
+       << GetDuration(extraction_start_time, extraction_stop_time)
+       << " seconds" << endl;
+
+  return 0;
+}
diff --git a/extractor/sample_alignment.txt b/extractor/sample_alignment.txt
new file mode 100644
index 00000000..80b446a4
--- /dev/null
+++ b/extractor/sample_alignment.txt
@@ -0,0 +1,2 @@
+0-0 1-1 2-2
+1-0 2-1
diff --git a/extractor/sample_bitext.txt b/extractor/sample_bitext.txt
new file mode 100644
index 00000000..93d6b39d
--- /dev/null
+++ b/extractor/sample_bitext.txt
@@ -0,0 +1,2 @@
+ana are mere . ||| anna has apples .
+ana bea mult lapte . ||| anna drinks a lot of milk .
diff --git a/extractor/sampler.cc b/extractor/sampler.cc
new file mode 100644
index 00000000..d81956b5
--- /dev/null
+++ b/extractor/sampler.cc
@@ -0,0 +1,46 @@
+#include "sampler.h"
+
+#include "phrase_location.h"
+#include "suffix_array.h"
+
+namespace extractor {
+
+Sampler::Sampler(shared_ptr<SuffixArray> suffix_array, int max_samples) :
+    suffix_array(suffix_array), max_samples(max_samples) {}
+
+Sampler::Sampler() {}
+
+Sampler::~Sampler() {}
+
+PhraseLocation Sampler::Sample(const PhraseLocation& location) const {
+  vector<int> sample;
+  int num_subpatterns;
+  if (location.matchings == NULL) {
+    // Sample suffix array range.
+    num_subpatterns = 1;
+    int low = location.sa_low, high = location.sa_high;
+    double step = max(1.0, (double) (high - low) / max_samples);
+    for (double i = low; i < high && sample.size() < max_samples; i += step) {
+      sample.push_back(suffix_array->GetSuffix(Round(i)));
+    }
+  } else {
+    // Sample vector of occurrences.
+    num_subpatterns = location.num_subpatterns;
+    int num_matchings = location.matchings->size() / num_subpatterns;
+    double step = max(1.0, (double) num_matchings / max_samples);
+    for (double i = 0, num_samples = 0;
+         i < num_matchings && num_samples < max_samples;
+         i += step, ++num_samples) {
+      int start = Round(i) * num_subpatterns;
+      sample.insert(sample.end(), location.matchings->begin() + start,
+          location.matchings->begin() + start + num_subpatterns);
+    }
+  }
+  return PhraseLocation(sample, num_subpatterns);
+}
+
+int Sampler::Round(double x) const {
+  return x + 0.5;
+}
+
+} // namespace extractor
diff --git a/extractor/sampler.h b/extractor/sampler.h
new file mode 100644
index 00000000..be4aa1bb
--- /dev/null
+++ b/extractor/sampler.h
@@ -0,0 +1,38 @@
+#ifndef _SAMPLER_H_
+#define _SAMPLER_H_
+
+#include <memory>
+
+using namespace std;
+
+namespace extractor {
+
+class PhraseLocation;
+class SuffixArray;
+
+/**
+ * Provides uniform sampling for a PhraseLocation.
+ */
+class Sampler {
+ public:
+  Sampler(shared_ptr<SuffixArray> suffix_array, int max_samples);
+
+  virtual ~Sampler();
+
+  // Samples uniformly at most max_samples phrase occurrences.
+  virtual PhraseLocation Sample(const PhraseLocation& location) const;
+
+ protected:
+  Sampler();
+
+ private:
+  // Round floating point number to the nearest integer.
+  int Round(double x) const;
+
+  shared_ptr<SuffixArray> suffix_array;
+  int max_samples;
+};
+
+} // namespace extractor
+
+#endif
diff --git a/extractor/sampler_test.cc b/extractor/sampler_test.cc
new file mode 100644
index 00000000..e9abebfa
--- /dev/null
+++ b/extractor/sampler_test.cc
@@ -0,0 +1,74 @@
+#include <gtest/gtest.h>
+
+#include <memory>
+
+#include "mocks/mock_suffix_array.h"
+#include "phrase_location.h"
+#include "sampler.h"
+
+using namespace std;
+using namespace ::testing;
+
+namespace extractor {
+namespace {
+
+class SamplerTest : public Test {
+ protected:
+  virtual void SetUp() {
+    suffix_array = make_shared<MockSuffixArray>();
+    for (int i = 0; i < 10; ++i) {
+      EXPECT_CALL(*suffix_array, GetSuffix(i)).WillRepeatedly(Return(i));
+    }
+  }
+
+  shared_ptr<MockSuffixArray> suffix_array;
+  shared_ptr<Sampler> sampler;
+};
+
+TEST_F(SamplerTest, TestSuffixArrayRange) {
+  PhraseLocation location(0, 10);
+
+  sampler = make_shared<Sampler>(suffix_array, 1);
+  vector<int> expected_locations = {0};
+  EXPECT_EQ(PhraseLocation(expected_locations, 1), sampler->Sample(location));
+
+  sampler = make_shared<Sampler>(suffix_array, 2);
+  expected_locations = {0, 5};
+  EXPECT_EQ(PhraseLocation(expected_locations, 1), sampler->Sample(location));
+
+  sampler = make_shared<Sampler>(suffix_array, 3);
+  expected_locations = {0, 3, 7};
+  EXPECT_EQ(PhraseLocation(expected_locations, 1), sampler->Sample(location));
+
+  sampler = make_shared<Sampler>(suffix_array, 4);
+  expected_locations = {0, 3, 5, 8};
+  EXPECT_EQ(PhraseLocation(expected_locations, 1), sampler->Sample(location));
+
+  sampler = make_shared<Sampler>(suffix_array, 100);
+  expected_locations = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
+  EXPECT_EQ(PhraseLocation(expected_locations, 1), sampler->Sample(location));
+}
+
+TEST_F(SamplerTest, TestSubstringsSample) {
+  vector<int> locations = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
+  PhraseLocation location(locations, 2);
+
+  sampler = make_shared<Sampler>(suffix_array, 1);
+  vector<int> expected_locations = {0, 1};
+  EXPECT_EQ(PhraseLocation(expected_locations, 2), sampler->Sample(location));
+
+  sampler = make_shared<Sampler>(suffix_array, 2);
+  expected_locations = {0, 1, 6, 7};
+  EXPECT_EQ(PhraseLocation(expected_locations, 2), sampler->Sample(location));
+
+  sampler = make_shared<Sampler>(suffix_array, 3);
+  expected_locations = {0, 1, 4, 5, 6, 7};
+  EXPECT_EQ(PhraseLocation(expected_locations, 2), sampler->Sample(location));
+
+  sampler = make_shared<Sampler>(suffix_array, 7);
+  expected_locations = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
+  EXPECT_EQ(PhraseLocation(expected_locations, 2), sampler->Sample(location));
+}
+
+} // namespace
+} // namespace extractor
diff --git a/extractor/scorer.cc b/extractor/scorer.cc
new file mode 100644
index 00000000..d3ebf1c9
--- /dev/null
+++ b/extractor/scorer.cc
@@ -0,0 +1,30 @@
+#include "scorer.h"
+
+#include "features/feature.h"
+
+namespace extractor {
+
+Scorer::Scorer(const vector<shared_ptr<features::Feature> >& features) :
+    features(features) {}
+
+Scorer::Scorer() {}
+
+Scorer::~Scorer() {}
+
+vector<double> Scorer::Score(const features::FeatureContext& context) const {
+  vector<double> scores;
+  for (auto feature: features) {
+    scores.push_back(feature->Score(context));
+  }
+  return scores;
+}
+
+vector<string> Scorer::GetFeatureNames() const {
+  vector<string> feature_names;
+  for (auto feature: features) {
+    feature_names.push_back(feature->GetName());
+  }
+  return feature_names;
+}
+
+} // namespace extractor
diff --git a/extractor/scorer.h b/extractor/scorer.h
new file mode 100644
index 00000000..af8a3b10
--- /dev/null
+++ b/extractor/scorer.h
@@ -0,0 +1,41 @@
+#ifndef _SCORER_H_
+#define _SCORER_H_
+
+#include <memory>
+#include <string>
+#include <vector>
+
+using namespace std;
+
+namespace extractor {
+
+namespace features {
+  class Feature;
+  class FeatureContext;
+} // namespace features
+
+/**
+ * Computes the feature scores for a source-target phrase pair.
+ */
+class Scorer {
+ public:
+  Scorer(const vector<shared_ptr<features::Feature> >& features);
+
+  virtual ~Scorer();
+
+  // Computes the feature score for the given context.
+  virtual vector<double> Score(const features::FeatureContext& context) const;
+
+  // Returns the set of feature names used to score any context.
+  virtual vector<string> GetFeatureNames() const;
+
+ protected:
+  Scorer();
+
+ private:
+  vector<shared_ptr<features::Feature> > features;
+};
+
+} // namespace extractor
+
+#endif
diff --git a/extractor/scorer_test.cc b/extractor/scorer_test.cc
new file mode 100644
index 00000000..3a09c9cc
--- /dev/null
+++ b/extractor/scorer_test.cc
@@ -0,0 +1,49 @@
+#include <gtest/gtest.h>
+
+#include <memory>
+#include <string>
+#include <vector>
+
+#include "mocks/mock_feature.h"
+#include "scorer.h"
+
+using namespace std;
+using namespace ::testing;
+
+namespace extractor {
+namespace {
+
+class ScorerTest : public Test {
+ protected:
+  virtual void SetUp() {
+    feature1 = make_shared<features::MockFeature>();
+    EXPECT_CALL(*feature1, Score(_)).WillRepeatedly(Return(0.5));
+    EXPECT_CALL(*feature1, GetName()).WillRepeatedly(Return("f1"));
+
+    feature2 = make_shared<features::MockFeature>();
+    EXPECT_CALL(*feature2, Score(_)).WillRepeatedly(Return(-1.3));
+    EXPECT_CALL(*feature2, GetName()).WillRepeatedly(Return("f2"));
+
+    vector<shared_ptr<features::Feature> > features = {feature1, feature2};
+    scorer = make_shared<Scorer>(features);
+  }
+
+  shared_ptr<features::MockFeature> feature1;
+  shared_ptr<features::MockFeature> feature2;
+  shared_ptr<Scorer> scorer;
+};
+
+TEST_F(ScorerTest, TestScore) {
+  vector<double> expected_scores = {0.5, -1.3};
+  Phrase phrase;
+  features::FeatureContext context(phrase, phrase, 0.3, 2, 11);
+  EXPECT_EQ(expected_scores, scorer->Score(context));
+}
+
+TEST_F(ScorerTest, TestGetNames) {
+  vector<string> expected_names = {"f1", "f2"};
+  EXPECT_EQ(expected_names, scorer->GetFeatureNames());
+}
+
+} // namespace
+} // namespace extractor
diff --git a/extractor/suffix_array.cc b/extractor/suffix_array.cc
new file mode 100644
index 00000000..65b2d581
--- /dev/null
+++ b/extractor/suffix_array.cc
@@ -0,0 +1,235 @@
+#include "suffix_array.h"
+
+#include <cassert>
+#include <chrono>
+#include <iostream>
+#include <string>
+#include <vector>
+
+#include "data_array.h"
+#include "phrase_location.h"
+#include "time_util.h"
+
+namespace fs = boost::filesystem;
+using namespace std;
+using namespace chrono;
+
+namespace extractor {
+
+SuffixArray::SuffixArray(shared_ptr<DataArray> data_array) :
+    data_array(data_array) {
+  BuildSuffixArray();
+}
+
+SuffixArray::SuffixArray() {}
+
+SuffixArray::~SuffixArray() {}
+
+void SuffixArray::BuildSuffixArray() {
+  vector<int> groups = data_array->GetData();
+  groups.reserve(groups.size() + 1);
+  groups.push_back(DataArray::NULL_WORD);
+  suffix_array.resize(groups.size());
+  word_start.resize(data_array->GetVocabularySize() + 1);
+
+  InitialBucketSort(groups);
+
+  int combined_group_size = 0;
+  for (size_t i = 1; i < word_start.size(); ++i) {
+    if (word_start[i] - word_start[i - 1] == 1) {
+      ++combined_group_size;
+      suffix_array[word_start[i] - combined_group_size] = -combined_group_size;
+    } else {
+      combined_group_size = 0;
+    }
+  }
+
+  PrefixDoublingSort(groups);
+  cerr << "\tFinalizing sort..." << endl;
+
+  for (size_t i = 0; i < groups.size(); ++i) {
+    suffix_array[groups[i]] = i;
+  }
+}
+
+void SuffixArray::InitialBucketSort(vector<int>& groups) {
+  Clock::time_point start_time = Clock::now();
+  for (size_t i = 0; i < groups.size(); ++i) {
+    ++word_start[groups[i]];
+  }
+
+  for (size_t i = 1; i < word_start.size(); ++i) {
+    word_start[i] += word_start[i - 1];
+  }
+
+  for (size_t i = 0; i < groups.size(); ++i) {
+    --word_start[groups[i]];
+    suffix_array[word_start[groups[i]]] = i;
+  }
+
+  for (size_t i = 0; i < suffix_array.size(); ++i) {
+    groups[i] = word_start[groups[i] + 1] - 1;
+  }
+  Clock::time_point stop_time = Clock::now();
+  cerr << "\tBucket sort took " << GetDuration(start_time, stop_time)
+       << " seconds" << endl;
+}
+
+void SuffixArray::PrefixDoublingSort(vector<int>& groups) {
+  int step = 1;
+  while (suffix_array[0] != -suffix_array.size()) {
+    int combined_group_size = 0;
+    int i = 0;
+    while (i < suffix_array.size()) {
+      if (suffix_array[i] < 0) {
+        int skip = -suffix_array[i];
+        combined_group_size += skip;
+        i += skip;
+        suffix_array[i - combined_group_size] = -combined_group_size;
+      } else {
+        combined_group_size = 0;
+        int j = groups[suffix_array[i]];
+        TernaryQuicksort(i, j, step, groups);
+        i = j + 1;
+      }
+    }
+    step *= 2;
+  }
+}
+
+void SuffixArray::TernaryQuicksort(int left, int right, int step,
+    vector<int>& groups) {
+  if (left > right) {
+    return;
+  }
+
+  int pivot = left + rand() % (right - left + 1);
+  int pivot_value = groups[suffix_array[pivot] + step];
+  swap(suffix_array[pivot], suffix_array[left]);
+  int mid_left = left, mid_right = left;
+  for (int i = left + 1; i <= right; ++i) {
+    if (groups[suffix_array[i] + step] < pivot_value) {
+      ++mid_right;
+      int temp = suffix_array[i];
+      suffix_array[i] = suffix_array[mid_right];
+      suffix_array[mid_right] = suffix_array[mid_left];
+      suffix_array[mid_left] = temp;
+      ++mid_left;
+    } else if (groups[suffix_array[i] + step] == pivot_value) {
+      ++mid_right;
+      int temp = suffix_array[i];
+      suffix_array[i] = suffix_array[mid_right];
+      suffix_array[mid_right] = temp;
+    }
+  }
+
+  TernaryQuicksort(left, mid_left - 1, step, groups);
+
+  if (mid_left == mid_right) {
+    groups[suffix_array[mid_left]] = mid_left;
+    suffix_array[mid_left] = -1;
+  } else {
+    for (int i = mid_left; i <= mid_right; ++i) {
+      groups[suffix_array[i]] = mid_right;
+    }
+  }
+
+  TernaryQuicksort(mid_right + 1, right, step, groups);
+}
+
+vector<int> SuffixArray::BuildLCPArray() const {
+  Clock::time_point start_time = Clock::now();
+  cerr << "\tConstructing LCP array..." << endl;
+
+  vector<int> lcp(suffix_array.size());
+  vector<int> rank(suffix_array.size());
+  const vector<int>& data = data_array->GetData();
+
+  for (size_t i = 0; i < suffix_array.size(); ++i) {
+    rank[suffix_array[i]] = i;
+  }
+
+  int prefix_len = 0;
+  for (size_t i = 0; i < suffix_array.size(); ++i) {
+    if (rank[i] == 0) {
+      lcp[rank[i]] = -1;
+    } else {
+      int j = suffix_array[rank[i] - 1];
+      while (i + prefix_len < data.size() && j + prefix_len < data.size()
+          && data[i + prefix_len] == data[j + prefix_len]) {
+        ++prefix_len;
+      }
+      lcp[rank[i]] = prefix_len;
+    }
+
+    if (prefix_len > 0) {
+      --prefix_len;
+    }
+  }
+
+  Clock::time_point stop_time = Clock::now();
+  cerr << "\tConstructing LCP took "
+       << GetDuration(start_time, stop_time) << " seconds" << endl;
+
+  return lcp;
+}
+
+int SuffixArray::GetSuffix(int rank) const {
+  return suffix_array[rank];
+}
+
+int SuffixArray::GetSize() const {
+  return suffix_array.size();
+}
+
+shared_ptr<DataArray> SuffixArray::GetData() const {
+  return data_array;
+}
+
+void SuffixArray::WriteBinary(const fs::path& filepath) const {
+  FILE* file = fopen(filepath.string().c_str(), "w");
+  assert(file);
+  data_array->WriteBinary(file);
+
+  int size = suffix_array.size();
+  fwrite(&size, sizeof(int), 1, file);
+  fwrite(suffix_array.data(), sizeof(int), size, file);
+
+  size = word_start.size();
+  fwrite(&size, sizeof(int), 1, file);
+  fwrite(word_start.data(), sizeof(int), size, file);
+}
+
+PhraseLocation SuffixArray::Lookup(int low, int high, const string& word,
+                                   int offset) const {
+  if (!data_array->HasWord(word)) {
+    // Return empty phrase location.
+    return PhraseLocation(0, 0);
+  }
+
+  int word_id = data_array->GetWordId(word);
+  if (offset == 0) {
+    return PhraseLocation(word_start[word_id], word_start[word_id + 1]);
+  }
+
+  return PhraseLocation(LookupRangeStart(low, high, word_id, offset),
+      LookupRangeStart(low, high, word_id + 1, offset));
+}
+
+int SuffixArray::LookupRangeStart(int low, int high, int word_id,
+                                  int offset) const {
+  int result = high;
+  while (low < high) {
+    int middle = low + (high - low) / 2;
+    if (suffix_array[middle] + offset >= data_array->GetSize() ||
+        data_array->AtIndex(suffix_array[middle] + offset) < word_id) {
+      low = middle + 1;
+    } else {
+      result = middle;
+      high = middle;
+    }
+  }
+  return result;
+}
+
+} // namespace extractor
diff --git a/extractor/suffix_array.h b/extractor/suffix_array.h
new file mode 100644
index 00000000..bf731d79
--- /dev/null
+++ b/extractor/suffix_array.h
@@ -0,0 +1,75 @@
+#ifndef _SUFFIX_ARRAY_H_
+#define _SUFFIX_ARRAY_H_
+
+#include <memory>
+#include <string>
+#include <vector>
+
+#include <boost/filesystem.hpp>
+
+namespace fs = boost::filesystem;
+using namespace std;
+
+namespace extractor {
+
+class DataArray;
+class PhraseLocation;
+
+class SuffixArray {
+ public:
+  // Creates a suffix array from a data array.
+  SuffixArray(shared_ptr<DataArray> data_array);
+
+  virtual ~SuffixArray();
+
+  // Returns the size of the suffix array.
+  virtual int GetSize() const;
+
+  // Returns the data array on top of which the suffix array is constructed.
+  virtual shared_ptr<DataArray> GetData() const;
+
+  // Constructs the longest-common-prefix array using the algorithm of Kasai et
+  // al. (2001).
+  virtual vector<int> BuildLCPArray() const;
+
+  // Returns the i-th suffix.
+  virtual int GetSuffix(int rank) const;
+
+  // Given the range in which a phrase is located and the next word, returns the
+  // range corresponding to the phrase extended with the next word.
+  virtual PhraseLocation Lookup(int low, int high, const string& word,
+                                int offset) const;
+
+  void WriteBinary(const fs::path& filepath) const;
+
+ protected:
+  SuffixArray();
+
+ private:
+  // Constructs the suffix array using the algorithm of Larsson and Sadakane
+  // (1999).
+  void BuildSuffixArray();
+
+  // Bucket sort on the data array (used for initializing the construction of
+  // the suffix array.)
+  void InitialBucketSort(vector<int>& groups);
+
+  void TernaryQuicksort(int left, int right, int step, vector<int>& groups);
+
+  // Constructs the suffix array in log(n) steps by doubling the length of the
+  // suffixes at each step.
+  void PrefixDoublingSort(vector<int>& groups);
+
+  // Given a [low, high) range in the suffix array in which all elements have
+  // the first offset-1 values the same, it returns the first position where the
+  // offset value is greater or equal to word_id.
+  int LookupRangeStart(int low, int high, int word_id, int offset) const;
+
+  shared_ptr<DataArray> data_array;
+  vector<int> suffix_array;
+  vector<int> word_start;
+};
+
+} // namespace extractor
+
+#endif
diff --git a/extractor/suffix_array_test.cc b/extractor/suffix_array_test.cc
new file mode 100644
index 00000000..8431a16e
--- /dev/null
+++ b/extractor/suffix_array_test.cc
@@ -0,0 +1,78 @@
+#include <gtest/gtest.h>
+
+#include "mocks/mock_data_array.h"
+#include "phrase_location.h"
+#include "suffix_array.h"
+
+#include <vector>
+
+using namespace std;
+using namespace ::testing;
+
+namespace extractor {
+namespace {
+
+class SuffixArrayTest : public Test {
+ protected:
+  virtual void SetUp() {
+    data = {6, 4, 1, 2, 4, 5, 3, 4, 6, 6, 4, 1, 2};
+    data_array = make_shared<MockDataArray>();
+    EXPECT_CALL(*data_array, GetData()).WillRepeatedly(ReturnRef(data));
+    EXPECT_CALL(*data_array, GetVocabularySize()).WillRepeatedly(Return(7));
+    EXPECT_CALL(*data_array, GetSize()).WillRepeatedly(Return(13));
+    suffix_array = make_shared<SuffixArray>(data_array);
+  }
+
+  vector<int> data;
+  shared_ptr<SuffixArray> suffix_array;
+  shared_ptr<MockDataArray> data_array;
+};
+
+TEST_F(SuffixArrayTest, TestData) {
+  EXPECT_EQ(data_array, suffix_array->GetData());
+  EXPECT_EQ(14, suffix_array->GetSize());
+}
+
+TEST_F(SuffixArrayTest, TestBuildSuffixArray) {
+  vector<int> expected_suffix_array =
+      {13, 11, 2, 12, 3, 6, 10, 1, 4, 7, 5, 9, 0, 8};
+  for (size_t i = 0; i < expected_suffix_array.size(); ++i) {
+    EXPECT_EQ(expected_suffix_array[i], suffix_array->GetSuffix(i));
+  }
+}
+
+TEST_F(SuffixArrayTest, TestBuildLCP) {
+  vector<int> expected_lcp = {-1, 0, 2, 0, 1, 0, 0, 3, 1, 1, 0, 0, 4, 1};
+  EXPECT_EQ(expected_lcp, suffix_array->BuildLCPArray());
+}
+
+TEST_F(SuffixArrayTest, TestLookup) {
+  for (size_t i = 0; i < data.size(); ++i) {
+    EXPECT_CALL(*data_array, AtIndex(i)).WillRepeatedly(Return(data[i]));
+  }
+
+  EXPECT_CALL(*data_array, HasWord("word1")).WillRepeatedly(Return(true));
+  EXPECT_CALL(*data_array, GetWordId("word1")).WillRepeatedly(Return(6));
+  EXPECT_EQ(PhraseLocation(11, 14), suffix_array->Lookup(0, 14, "word1", 0));
+
+  EXPECT_CALL(*data_array, HasWord("word2")).WillRepeatedly(Return(false));
+  EXPECT_EQ(PhraseLocation(0, 0), suffix_array->Lookup(0, 14, "word2", 0));
+
+  EXPECT_CALL(*data_array, HasWord("word3")).WillRepeatedly(Return(true));
+  EXPECT_CALL(*data_array, GetWordId("word3")).WillRepeatedly(Return(4));
+  EXPECT_EQ(PhraseLocation(11, 13), suffix_array->Lookup(11, 14, "word3", 1));
+
+  EXPECT_CALL(*data_array, HasWord("word4")).WillRepeatedly(Return(true));
+  EXPECT_CALL(*data_array, GetWordId("word4")).WillRepeatedly(Return(1));
+  EXPECT_EQ(PhraseLocation(11, 13), suffix_array->Lookup(11, 13, "word4", 2));
+
+  EXPECT_CALL(*data_array, HasWord("word5")).WillRepeatedly(Return(true));
+  EXPECT_CALL(*data_array, GetWordId("word5")).WillRepeatedly(Return(2));
+  EXPECT_EQ(PhraseLocation(11, 13), suffix_array->Lookup(11, 13, "word5", 3));
+
+  EXPECT_EQ(PhraseLocation(12, 13), suffix_array->Lookup(11, 13, "word3", 4));
+  EXPECT_EQ(PhraseLocation(11, 11), suffix_array->Lookup(11, 13, "word5", 1));
+}
+
+} // namespace
+} // namespace extractor
diff --git a/extractor/target_phrase_extractor.cc b/extractor/target_phrase_extractor.cc
new file mode 100644
index 00000000..2b8a2e4a
--- /dev/null
+++ b/extractor/target_phrase_extractor.cc
@@ -0,0 +1,158 @@
+#include "target_phrase_extractor.h"
+
+#include <unordered_set>
+
+#include "alignment.h"
+#include "data_array.h"
+#include "phrase.h"
+#include "phrase_builder.h"
+#include "rule_extractor_helper.h"
+#include "vocabulary.h"
+
+using namespace std;
+
+namespace extractor {
+
+TargetPhraseExtractor::TargetPhraseExtractor(
+    shared_ptr<DataArray> target_data_array,
+    shared_ptr<Alignment> alignment,
+    shared_ptr<PhraseBuilder> phrase_builder,
+    shared_ptr<RuleExtractorHelper> helper,
+    shared_ptr<Vocabulary> vocabulary,
+    int max_rule_span,
+    bool require_tight_phrases) :
+    target_data_array(target_data_array),
+    alignment(alignment),
+    phrase_builder(phrase_builder),
+    helper(helper),
+    vocabulary(vocabulary),
+    max_rule_span(max_rule_span),
+    require_tight_phrases(require_tight_phrases) {}
+
+TargetPhraseExtractor::TargetPhraseExtractor() {}
+
+TargetPhraseExtractor::~TargetPhraseExtractor() {}
+
+vector<pair<Phrase, PhraseAlignment> > TargetPhraseExtractor::ExtractPhrases(
+    const vector<pair<int, int> >& target_gaps, const vector<int>& target_low,
+    int target_phrase_low, int target_phrase_high,
+    const unordered_map<int, int>& source_indexes, int sentence_id) const {
+  int target_sent_len = target_data_array->GetSentenceLength(sentence_id);
+
+  vector<int> target_gap_order = helper->GetGapOrder(target_gaps);
+
+  int target_x_low = target_phrase_low, target_x_high = target_phrase_high;
+  if (!require_tight_phrases) {
+    // Extend loose target phrase to the left.
+    while (target_x_low > 0 &&
+           target_phrase_high - target_x_low < max_rule_span &&
+           target_low[target_x_low - 1] == -1) {
+      --target_x_low;
+    }
+    // Extend loose target phrase to the right.
+    while (target_x_high < target_sent_len &&
+           target_x_high - target_phrase_low < max_rule_span &&
+           target_low[target_x_high] == -1) {
+      ++target_x_high;
+    }
+  }
+
+  vector<pair<int, int> > gaps(target_gaps.size());
+  for (size_t i = 0; i < gaps.size(); ++i) {
+    gaps[i] = target_gaps[target_gap_order[i]];
+    if (!require_tight_phrases) {
+      // Extend gap to the left.
+      while (gaps[i].first > target_x_low &&
+             target_low[gaps[i].first - 1] == -1) {
+        --gaps[i].first;
+      }
+      // Extend gap to the right.
+      while (gaps[i].second < target_x_high &&
+             target_low[gaps[i].second] == -1) {
+        ++gaps[i].second;
+      }
+    }
+  }
+
+  // Compute the range in which each chunk may start or end. (Even indexes
+  // represent the range in which the chunk may start, odd indexes represent the
+  // range in which the chunk may end.)
+  vector<pair<int, int> > ranges(2 * gaps.size() + 2);
+  ranges.front() = make_pair(target_x_low, target_phrase_low);
+  ranges.back() = make_pair(target_phrase_high, target_x_high);
+  for (size_t i = 0; i < gaps.size(); ++i) {
+    int j = target_gap_order[i];
+    ranges[i * 2 + 1] = make_pair(gaps[i].first, target_gaps[j].first);
+    ranges[i * 2 + 2] = make_pair(target_gaps[j].second, gaps[i].second);
+  }
+
+  vector<pair<Phrase, PhraseAlignment> > target_phrases;
+  vector<int> subpatterns(ranges.size());
+  GeneratePhrases(target_phrases, ranges, 0, subpatterns, target_gap_order,
+                  target_phrase_low, target_phrase_high, source_indexes,
+                  sentence_id);
+  return target_phrases;
+}
+
+void TargetPhraseExtractor::GeneratePhrases(
+    vector<pair<Phrase, PhraseAlignment> >& target_phrases,
+    const vector<pair<int, int> >& ranges, int index, vector<int>& subpatterns,
+    const vector<int>& target_gap_order, int target_phrase_low,
+    int target_phrase_high, const unordered_map<int, int>& source_indexes,
+    int sentence_id) const {
+  if (index >= ranges.size()) {
+    if (subpatterns.back() - subpatterns.front() > max_rule_span) {
+      return;
+    }
+
+    vector<int> symbols;
+    unordered_map<int, int> target_indexes;
+
+    // Construct target phrase chunk by chunk.
+    int target_sent_start = target_data_array->GetSentenceStart(sentence_id);
+    for (size_t i = 0; i * 2 < subpatterns.size(); ++i) {
+      for (size_t j = subpatterns[i * 2]; j < subpatterns[i * 2 + 1]; ++j) {
+        target_indexes[j] = symbols.size();
+        string target_word = target_data_array->GetWordAtIndex(
+            target_sent_start + j);
+        symbols.push_back(vocabulary->GetTerminalIndex(target_word));
+      }
+      if (i < target_gap_order.size()) {
+        symbols.push_back(vocabulary->GetNonterminalIndex(
+            target_gap_order[i] + 1));
+      }
+    }
+
+    // Construct the alignment between the source and the target phrase.
+    vector<pair<int, int> > links = alignment->GetLinks(sentence_id);
+    vector<pair<int, int> > alignment;
+    for (pair<int, int> link: links) {
+      if (target_indexes.count(link.second)) {
+        alignment.push_back(make_pair(source_indexes.find(link.first)->second,
+                                      target_indexes[link.second]));
+      }
+    }
+
+    Phrase target_phrase = phrase_builder->Build(symbols);
+    target_phrases.push_back(make_pair(target_phrase, alignment));
+    return;
+  }
+
+  subpatterns[index] = ranges[index].first;
+  if (index > 0) {
+    subpatterns[index] = max(subpatterns[index], subpatterns[index - 1]);
+  }
+  // Choose every possible combination of [start, end) for the current chunk.
+  while (subpatterns[index] <= ranges[index].second) {
+    subpatterns[index + 1] = max(subpatterns[index], ranges[index + 1].first);
+    while (subpatterns[index + 1] <= ranges[index + 1].second) {
+      GeneratePhrases(target_phrases, ranges, index + 2, subpatterns,
+                      target_gap_order, target_phrase_low, target_phrase_high,
+                      source_indexes, sentence_id);
+      ++subpatterns[index + 1];
+    }
+    ++subpatterns[index];
+  }
+}
+
+} // namespace extractor
diff --git a/extractor/target_phrase_extractor.h b/extractor/target_phrase_extractor.h
new file mode 100644
index 00000000..289bae2f
--- /dev/null
+++ b/extractor/target_phrase_extractor.h
@@ -0,0 +1,64 @@
+#ifndef _TARGET_PHRASE_EXTRACTOR_H_
+#define _TARGET_PHRASE_EXTRACTOR_H_
+
+#include <memory>
+#include <unordered_map>
+#include <vector>
+
+using namespace std;
+
+namespace extractor {
+
+typedef vector<pair<int, int> > PhraseAlignment;
+
+class Alignment;
+class DataArray;
+class Phrase;
+class PhraseBuilder;
+class RuleExtractorHelper;
+class Vocabulary;
+
+class TargetPhraseExtractor {
+ public:
+  TargetPhraseExtractor(shared_ptr<DataArray> target_data_array,
+                        shared_ptr<Alignment> alignment,
+                        shared_ptr<PhraseBuilder> phrase_builder,
+                        shared_ptr<RuleExtractorHelper> helper,
+                        shared_ptr<Vocabulary> vocabulary,
+                        int max_rule_span,
+                        bool require_tight_phrases);
+
+  virtual ~TargetPhraseExtractor();
+
+  // Finds all the target phrases that can extracted from a span in the
+  // target sentence (matching the given set of target phrase gaps).
+  virtual vector<pair<Phrase, PhraseAlignment> > ExtractPhrases(
+      const vector<pair<int, int> >& target_gaps, const vector<int>& target_low,
+      int target_phrase_low, int target_phrase_high,
+      const unordered_map<int, int>& source_indexes, int sentence_id) const;
+
+ protected:
+  TargetPhraseExtractor();
+
+ private:
+  // Computes the cartesian product over the sets of possible target phrase
+  // chunks.
+  void GeneratePhrases(
+      vector<pair<Phrase, PhraseAlignment> >& target_phrases,
+      const vector<pair<int, int> >& ranges, int index,
+      vector<int>& subpatterns, const vector<int>& target_gap_order,
+      int target_phrase_low, int target_phrase_high,
+      const unordered_map<int, int>& source_indexes, int sentence_id) const;
+
+  shared_ptr<DataArray> target_data_array;
+  shared_ptr<Alignment> alignment;
+  shared_ptr<PhraseBuilder> phrase_builder;
+  shared_ptr<RuleExtractorHelper> helper;
+  shared_ptr<Vocabulary> vocabulary;
+  int max_rule_span;
+  bool require_tight_phrases;
+};
+
+} // namespace extractor
+
+#endif
diff --git a/extractor/target_phrase_extractor_test.cc b/extractor/target_phrase_extractor_test.cc
new file mode 100644
index 00000000..80927dee
--- /dev/null
+++ b/extractor/target_phrase_extractor_test.cc
@@ -0,0 +1,143 @@
+#include <gtest/gtest.h>
+
+#include <memory>
+#include <vector>
+
+#include "mocks/mock_alignment.h"
+#include "mocks/mock_data_array.h"
+#include "mocks/mock_rule_extractor_helper.h"
+#include "mocks/mock_vocabulary.h"
+#include "phrase.h"
+#include "phrase_builder.h"
+#include "target_phrase_extractor.h"
+
+using namespace std;
+using namespace ::testing;
+
+namespace extractor {
+namespace {
+
+class TargetPhraseExtractorTest : public Test {
+ protected:
+  virtual void SetUp() {
+    data_array = make_shared<MockDataArray>();
+    alignment = make_shared<MockAlignment>();
+    vocabulary = make_shared<MockVocabulary>();
+    phrase_builder = make_shared<PhraseBuilder>(vocabulary);
+    helper = make_shared<MockRuleExtractorHelper>();
+  }
+
+  shared_ptr<MockDataArray> data_array;
+  shared_ptr<MockAlignment> alignment;
+  shared_ptr<MockVocabulary> vocabulary;
+  shared_ptr<PhraseBuilder> phrase_builder;
+  shared_ptr<MockRuleExtractorHelper> helper;
+  shared_ptr<TargetPhraseExtractor> extractor;
+};
+
+TEST_F(TargetPhraseExtractorTest, TestExtractTightPhrasesTrue) {
+  EXPECT_CALL(*data_array, GetSentenceLength(1)).WillRepeatedly(Return(5));
+  EXPECT_CALL(*data_array, GetSentenceStart(1)).WillRepeatedly(Return(3));
+
+  vector<string> target_words = {"a", "b", "c", "d", "e"};
+  vector<int> target_symbols = {20, 21, 22, 23, 24};
+  for (size_t i = 0; i < target_words.size(); ++i) {
+    EXPECT_CALL(*data_array, GetWordAtIndex(i + 3))
+        .WillRepeatedly(Return(target_words[i]));
+    EXPECT_CALL(*vocabulary, GetTerminalIndex(target_words[i]))
+        .WillRepeatedly(Return(target_symbols[i]));
+    EXPECT_CALL(*vocabulary, GetTerminalValue(target_symbols[i]))
+        .WillRepeatedly(Return(target_words[i]));
+  }
+
+  vector<pair<int, int> > links = {
+    make_pair(0, 0), make_pair(1, 3), make_pair(2, 2), make_pair(3, 1),
+    make_pair(4, 4)
+  };
+  EXPECT_CALL(*alignment, GetLinks(1)).WillRepeatedly(Return(links));
+
+  vector<int> gap_order = {1, 0};
+  EXPECT_CALL(*helper, GetGapOrder(_)).WillRepeatedly(Return(gap_order));
+
+  extractor = make_shared<TargetPhraseExtractor>(
+      data_array, alignment, phrase_builder, helper, vocabulary, 10, true);
+
+  vector<pair<int, int> > target_gaps = {make_pair(3, 4), make_pair(1, 2)};
+  vector<int> target_low = {0, 3, 2, 1, 4};
+  unordered_map<int, int> source_indexes = {{0, 0}, {2, 2}, {4, 4}};
+
+  vector<pair<Phrase, PhraseAlignment> > results =  extractor->ExtractPhrases(
+      target_gaps, target_low, 0, 5, source_indexes, 1);
+  EXPECT_EQ(1, results.size());
+  vector<int> expected_symbols = {20, -2, 22, -1, 24};
+  EXPECT_EQ(expected_symbols, results[0].first.Get());
+  vector<string> expected_words = {"a", "c", "e"};
+  EXPECT_EQ(expected_words, results[0].first.GetWords());
+  vector<pair<int, int> > expected_alignment = {
+    make_pair(0, 0), make_pair(2, 2), make_pair(4, 4)
+  };
+  EXPECT_EQ(expected_alignment, results[0].second);
+}
+
+TEST_F(TargetPhraseExtractorTest, TestExtractPhrasesTightPhrasesFalse) {
+  vector<string> target_words = {"a", "b", "c", "d", "e", "f", "END_OF_LINE"};
+  vector<int> target_symbols = {20, 21, 22, 23, 24, 25, 1};
+  EXPECT_CALL(*data_array, GetSentenceLength(0)).WillRepeatedly(Return(6));
+  EXPECT_CALL(*data_array, GetSentenceStart(0)).WillRepeatedly(Return(0));
+
+  for (size_t i = 0; i < target_words.size(); ++i) {
+    EXPECT_CALL(*data_array, GetWordAtIndex(i))
+        .WillRepeatedly(Return(target_words[i]));
+    EXPECT_CALL(*vocabulary, GetTerminalIndex(target_words[i]))
+        .WillRepeatedly(Return(target_symbols[i]));
+    EXPECT_CALL(*vocabulary, GetTerminalValue(target_symbols[i]))
+        .WillRepeatedly(Return(target_words[i]));
+  }
+
+  vector<pair<int, int> > links = {make_pair(1, 1)};
+  EXPECT_CALL(*alignment, GetLinks(0)).WillRepeatedly(Return(links));
+
+  vector<int> gap_order = {0};
+  EXPECT_CALL(*helper, GetGapOrder(_)).WillRepeatedly(Return(gap_order));
+
+  extractor = make_shared<TargetPhraseExtractor>(
+      data_array, alignment, phrase_builder, helper, vocabulary, 10, false);
+
+  vector<pair<int, int> > target_gaps = {make_pair(2, 4)};
+  vector<int> target_low = {-1, 1, -1, -1, -1, -1};
+  unordered_map<int, int> source_indexes = {{1, 1}};
+
+  vector<pair<Phrase, PhraseAlignment> > results = extractor->ExtractPhrases(
+      target_gaps, target_low, 1, 5, source_indexes, 0);
+  EXPECT_EQ(10, results.size());
+
+  for (int i = 0; i < 2; ++i) {
+    for (int j = 4; j <= 6; ++j) {
+      for (int k = 4; k <= j; ++k) {
+        vector<string> expected_words;
+        for (int l = i; l < 2; ++l) {
+          expected_words.push_back(target_words[l]);
+        }
+        for (int l = k; l < j; ++l) {
+          expected_words.push_back(target_words[l]);
+        }
+
+        PhraseAlignment expected_alignment;
+        expected_alignment.push_back(make_pair(1, 1 - i));
+
+        bool found_expected_pair = false;
+        for (auto result: results) {
+          if (result.first.GetWords() == expected_words &&
+              result.second == expected_alignment) {
+            found_expected_pair = true;
+          }
+        }
+
+        EXPECT_TRUE(found_expected_pair);
+      }
+    }
+  }
+}
+
+} // namespace
+} // namespace extractor
diff --git a/extractor/time_util.cc b/extractor/time_util.cc
new file mode 100644
index 00000000..e46a0c3d
--- /dev/null
+++ b/extractor/time_util.cc
@@ -0,0 +1,10 @@
+#include "time_util.h"
+
+namespace extractor {
+
+double GetDuration(const Clock::time_point& start_time,
+                   const Clock::time_point& stop_time) {
+  return duration_cast<milliseconds>(stop_time - start_time).count() / 1000.0;
+}
+
+} // namespace extractor
diff --git a/extractor/time_util.h b/extractor/time_util.h
new file mode 100644
index 00000000..f7fd51d3
--- /dev/null
+++ b/extractor/time_util.h
@@ -0,0 +1,19 @@
+#ifndef _TIME_UTIL_H_
+#define _TIME_UTIL_H_
+
+#include <chrono>
+
+using namespace std;
+using namespace chrono;
+
+namespace extractor {
+
+typedef high_resolution_clock Clock;
+
+// Computes the duration in seconds of the specified time interval.
+double GetDuration(const Clock::time_point& start_time,
+                   const Clock::time_point& stop_time);
+
+} // namespace extractor
+
+#endif
diff --git a/extractor/translation_table.cc b/extractor/translation_table.cc
new file mode 100644
index 00000000..45da707a
--- /dev/null
+++ b/extractor/translation_table.cc
@@ -0,0 +1,126 @@
+#include "translation_table.h"
+
+#include <string>
+#include <vector>
+
+#include <boost/functional/hash.hpp>
+
+#include "alignment.h"
+#include "data_array.h"
+
+using namespace std;
+
+namespace extractor {
+
+TranslationTable::TranslationTable(shared_ptr<DataArray> source_data_array,
+                                   shared_ptr<DataArray> target_data_array,
+                                   shared_ptr<Alignment> alignment) :
+    source_data_array(source_data_array), target_data_array(target_data_array) {
+  const vector<int>& source_data = source_data_array->GetData();
+  const vector<int>& target_data = target_data_array->GetData();
+
+  unordered_map<int, int> source_links_count;
+  unordered_map<int, int> target_links_count;
+  unordered_map<pair<int, int>, int, PairHash> links_count;
+
+  // For each pair of aligned source target words increment their link count by
+  // 1. Unaligned words are paired with the NULL token.
+  for (size_t i = 0; i < source_data_array->GetNumSentences(); ++i) {
+    vector<pair<int, int> > links = alignment->GetLinks(i);
+    int source_start = source_data_array->GetSentenceStart(i);
+    int target_start = target_data_array->GetSentenceStart(i);
+    // Ignore END_OF_LINE markers.
+    int next_source_start = source_data_array->GetSentenceStart(i + 1) - 1;
+    int next_target_start = target_data_array->GetSentenceStart(i + 1) - 1;
+    vector<int> source_sentence(source_data.begin() + source_start,
+        source_data.begin() + next_source_start);
+    vector<int> target_sentence(target_data.begin() + target_start,
+        target_data.begin() + next_target_start);
+    vector<int> source_linked_words(source_sentence.size());
+    vector<int> target_linked_words(target_sentence.size());
+
+    for (pair<int, int> link: links) {
+      source_linked_words[link.first] = 1;
+      target_linked_words[link.second] = 1;
+      IncrementLinksCount(source_links_count, target_links_count, links_count,
+          source_sentence[link.first], target_sentence[link.second]);
+    }
+
+    for (size_t i = 0; i < source_sentence.size(); ++i) {
+      if (!source_linked_words[i]) {
+        IncrementLinksCount(source_links_count, target_links_count, links_count,
+                            source_sentence[i], DataArray::NULL_WORD);
+      }
+    }
+
+    for (size_t i = 0; i < target_sentence.size(); ++i) {
+      if (!target_linked_words[i]) {
+        IncrementLinksCount(source_links_count, target_links_count, links_count,
+                            DataArray::NULL_WORD, target_sentence[i]);
+      }
+    }
+  }
+
+  // Calculating:
+  //   p(e | f) = count(e, f) / count(f)
+  //   p(f | e) = count(e, f) / count(e)
+  for (pair<pair<int, int>, int> link_count: links_count) {
+    int source_word = link_count.first.first;
+    int target_word = link_count.first.second;
+    double score1 = 1.0 * link_count.second / source_links_count[source_word];
+    double score2 = 1.0 * link_count.second / target_links_count[target_word];
+    translation_probabilities[link_count.first] = make_pair(score1, score2);
+  }
+}
+
+TranslationTable::TranslationTable() {}
+
+TranslationTable::~TranslationTable() {}
+
+void TranslationTable::IncrementLinksCount(
+    unordered_map<int, int>& source_links_count,
+    unordered_map<int, int>& target_links_count,
+    unordered_map<pair<int, int>, int, PairHash>& links_count,
+    int source_word_id,
+    int target_word_id) const {
+  ++source_links_count[source_word_id];
+  ++target_links_count[target_word_id];
+  ++links_count[make_pair(source_word_id, target_word_id)];
+}
+
+double TranslationTable::GetTargetGivenSourceScore(
+    const string& source_word, const string& target_word) {
+  if (!source_data_array->HasWord(source_word) ||
+      !target_data_array->HasWord(target_word)) {
+    return -1;
+  }
+
+  int source_id = source_data_array->GetWordId(source_word);
+  int target_id = target_data_array->GetWordId(target_word);
+  return translation_probabilities[make_pair(source_id, target_id)].first;
+}
+
+double TranslationTable::GetSourceGivenTargetScore(
+    const string& source_word, const string& target_word) {
+  if (!source_data_array->HasWord(source_word) ||
+      !target_data_array->HasWord(target_word)) {
+    return -1;
+  }
+
+  int source_id = source_data_array->GetWordId(source_word);
+  int target_id = target_data_array->GetWordId(target_word);
+  return translation_probabilities[make_pair(source_id, target_id)].second;
+}
+
+void TranslationTable::WriteBinary(const fs::path& filepath) const {
+  FILE* file = fopen(filepath.string().c_str(), "w");
+
+  int size = translation_probabilities.size();
+  fwrite(&size, sizeof(int), 1, file);
+  for (auto entry: translation_probabilities) {
+    fwrite(&entry.first, sizeof(entry.first), 1, file);
+    fwrite(&entry.second, sizeof(entry.second), 1, file);
+  }
+}
+
+} // namespace extractor
diff --git a/extractor/translation_table.h b/extractor/translation_table.h
new file mode 100644
index 00000000..10504d3b
--- /dev/null
+++ b/extractor/translation_table.h
@@ -0,0 +1,63 @@
+#ifndef _TRANSLATION_TABLE_
+#define _TRANSLATION_TABLE_
+
+#include <memory>
+#include <string>
+#include <unordered_map>
+
+#include <boost/filesystem.hpp>
+#include <boost/functional/hash.hpp>
+
+using namespace std;
+namespace fs = boost::filesystem;
+
+namespace extractor {
+
+typedef boost::hash<pair<int, int> > PairHash;
+
+class Alignment;
+class DataArray;
+
+/**
+ * Bilexical table with conditional probabilities.
+ */
+class TranslationTable {
+ public:
+  TranslationTable(
+      shared_ptr<DataArray> source_data_array,
+      shared_ptr<DataArray> target_data_array,
+      shared_ptr<Alignment> alignment);
+
+  virtual ~TranslationTable();
+
+  // Returns p(e | f).
+  virtual double GetTargetGivenSourceScore(const string& source_word,
+                                           const string& target_word);
+
+  // Returns p(f | e).
+  virtual double GetSourceGivenTargetScore(const string& source_word,
+                                           const string& target_word);
+
+  void WriteBinary(const fs::path& filepath) const;
+
+ protected:
+  TranslationTable();
+
+ private:
+  // Increment links count for the given (f, e) word pair.
+  void IncrementLinksCount(
+      unordered_map<int, int>& source_links_count,
+      unordered_map<int, int>& target_links_count,
+      unordered_map<pair<int, int>, int, PairHash>& links_count,
+      int source_word_id,
+      int target_word_id) const;
+
+  shared_ptr<DataArray> source_data_array;
+  shared_ptr<DataArray> target_data_array;
+  unordered_map<pair<int, int>, pair<double, double>, PairHash>
+      translation_probabilities;
+};
+
+} // namespace extractor
+
+#endif
diff --git a/extractor/translation_table_test.cc b/extractor/translation_table_test.cc
new file mode 100644
index 00000000..051b5715
--- /dev/null
+++ b/extractor/translation_table_test.cc
@@ -0,0 +1,84 @@
+#include <gtest/gtest.h>
+
+#include <memory>
+#include <string>
+#include <vector>
+
+#include "mocks/mock_alignment.h"
+#include "mocks/mock_data_array.h"
+#include "translation_table.h"
+
+using namespace std;
+using namespace ::testing;
+
+namespace extractor {
+namespace {
+
+TEST(TranslationTableTest, TestScores) {
+  vector<string> words = {"a", "b", "c"};
+
+  vector<int> source_data = {2, 3, 2, 3, 4, 0, 2, 3, 6, 0, 2, 3, 6, 0};
+  vector<int> source_sentence_start = {0, 6, 10, 14};
+  shared_ptr<MockDataArray> source_data_array = make_shared<MockDataArray>();
+  EXPECT_CALL(*source_data_array, GetData())
+      .WillRepeatedly(ReturnRef(source_data));
+  EXPECT_CALL(*source_data_array, GetNumSentences())
+      .WillRepeatedly(Return(3));
+  for (size_t i = 0; i < source_sentence_start.size(); ++i) {
+    EXPECT_CALL(*source_data_array, GetSentenceStart(i))
+        .WillRepeatedly(Return(source_sentence_start[i]));
+  }
+  for (size_t i = 0; i < words.size(); ++i) {
+    EXPECT_CALL(*source_data_array, HasWord(words[i]))
+        .WillRepeatedly(Return(true));
+    EXPECT_CALL(*source_data_array, GetWordId(words[i]))
+        .WillRepeatedly(Return(i + 2));
+  }
+  EXPECT_CALL(*source_data_array, HasWord("d"))
+      .WillRepeatedly(Return(false));
+
+  vector<int> target_data = {2, 3, 2, 3, 4, 5, 0, 3, 6, 0, 2, 7, 0};
+  vector<int> target_sentence_start = {0, 7, 10, 13};
+  shared_ptr<MockDataArray> target_data_array = make_shared<MockDataArray>();
+  EXPECT_CALL(*target_data_array, GetData())
+      .WillRepeatedly(ReturnRef(target_data));
+  for (size_t i = 0; i < target_sentence_start.size(); ++i) {
+    EXPECT_CALL(*target_data_array, GetSentenceStart(i))
+        .WillRepeatedly(Return(target_sentence_start[i]));
+  }
+  for (size_t i = 0; i < words.size(); ++i) {
+    EXPECT_CALL(*target_data_array, HasWord(words[i]))
+        .WillRepeatedly(Return(true));
+    EXPECT_CALL(*target_data_array, GetWordId(words[i]))
+        .WillRepeatedly(Return(i + 2));
+  }
+  EXPECT_CALL(*target_data_array, HasWord("d"))
+      .WillRepeatedly(Return(false));
+
+  vector<pair<int, int> > links1 = {
+    make_pair(0, 0), make_pair(1, 1), make_pair(2, 2), make_pair(3, 3),
+    make_pair(4, 4), make_pair(4, 5)
+  };
+  vector<pair<int, int> > links2 = {make_pair(1, 0), make_pair(2, 1)};
+  vector<pair<int, int> > links3 = {make_pair(0, 0), make_pair(2, 1)};
+  shared_ptr<MockAlignment> alignment = make_shared<MockAlignment>();
+  EXPECT_CALL(*alignment, GetLinks(0)).WillRepeatedly(Return(links1));
+  EXPECT_CALL(*alignment, GetLinks(1)).WillRepeatedly(Return(links2));
+  EXPECT_CALL(*alignment, GetLinks(2)).WillRepeatedly(Return(links3));
+
+  shared_ptr<TranslationTable> table = make_shared<TranslationTable>(
+      source_data_array, target_data_array, alignment);
+
+  EXPECT_EQ(0.75, table->GetTargetGivenSourceScore("a", "a"));
+  EXPECT_EQ(0, table->GetTargetGivenSourceScore("a", "b"));
+  EXPECT_EQ(0.5, table->GetTargetGivenSourceScore("c", "c"));
+  EXPECT_EQ(-1, table->GetTargetGivenSourceScore("c", "d"));
+
+  EXPECT_EQ(1, table->GetSourceGivenTargetScore("a", "a"));
+  EXPECT_EQ(0, table->GetSourceGivenTargetScore("a", "b"));
+  EXPECT_EQ(1, table->GetSourceGivenTargetScore("c", "c"));
+  EXPECT_EQ(-1, table->GetSourceGivenTargetScore("c", "d"));
+}
+
+} // namespace
+} // namespace extractor
diff --git a/extractor/vocabulary.cc b/extractor/vocabulary.cc
new file mode 100644
index 00000000..15795d1e
--- /dev/null
+++ b/extractor/vocabulary.cc
@@ -0,0 +1,37 @@
+#include "vocabulary.h"
+
+namespace extractor {
+
+Vocabulary::~Vocabulary() {}
+
+int Vocabulary::GetTerminalIndex(const string& word) {
+  int word_id = -1;
+  #pragma omp critical (vocabulary)
+  {
+    if (!dictionary.count(word)) {
+      word_id = words.size();
+      dictionary[word] = word_id;
+      words.push_back(word);
+    } else {
+      word_id = dictionary[word];
+    }
+  }
+  return word_id;
+}
+
+int Vocabulary::GetNonterminalIndex(int position) {
+  return -position;
+}
+
+bool Vocabulary::IsTerminal(int symbol) {
+  return symbol >= 0;
+}
+
+string Vocabulary::GetTerminalValue(int symbol) {
+  string word;
+  #pragma omp critical (vocabulary)
+  word = words[symbol];
+  return word;
+}
+
+} // namespace extractor
diff --git a/extractor/vocabulary.h b/extractor/vocabulary.h
new file mode 100644
index 00000000..c8fd9411
--- /dev/null
+++ b/extractor/vocabulary.h
@@ -0,0 +1,48 @@
+#ifndef _VOCABULARY_H_
+#define _VOCABULARY_H_
+
+#include <string>
+#include <unordered_map>
+#include <vector>
+
+using namespace std;
+
+namespace extractor {
+
+/**
+ * Data structure for mapping words to word ids.
+ *
+ * This strucure contains words located in the frequent collocations and words
+ * encountered during the grammar extraction time. This dictionary is
+ * considerably smaller than the dictionaries in the data arrays (and so is the
+ * query time). Note that this is the single data structure that changes state
+ * and needs to have thread safe read/write operations.
+ *
+ * Note: For an experiment using different vocabulary instances for each thread,
+ * the running time did not improve implying that the critical regions do not
+ * cause bottlenecks.
+ */
+class Vocabulary {
+ public:
+  virtual ~Vocabulary();
+
+  // Returns the word id for the given word.
+  virtual int GetTerminalIndex(const string& word);
+
+  // Returns the id for a nonterminal located at the given position in a phrase.
+  int GetNonterminalIndex(int position);
+
+  // Checks if a symbol is a nonterminal.
+  bool IsTerminal(int symbol);
+
+  // Returns the word corresponding to the given word id.
+  virtual string GetTerminalValue(int symbol);
+
+ private:
+  unordered_map<string, int> dictionary;
+  vector<string> words;
+};
+
+} // namespace extractor
+
+#endif