The aim of this work is to examine the applicability of an algorithm for approximate frequency counting to act as an on-the-fly filter in the process of phrase table extraction in Statistical Machine Translation systems. Its implementation allows for the bulk of extracted phrase pairs to be much reduced with no significant loss to the ultimate quality of the phrase-based translation model as measured by the state-of-the-art evaluation measure BLEU. The result of this implementation is a fully working program, called eppex, capable of acting as an alternative to the existing tools for phrase table creation and filtration that are part of the open-source SMT system Moses. A substantial part of this work is devoted to the benchmarking of both the runtime performance and the quality of produced phrase tables achieved by the program when confronted with parallel training data comprised of 2 billions of words. Powered by TCPDF (www.tcpdf.org)

Szemerédi's Regularity Lemma is powerful tool in Graph Theory, yielding many applications in areas such as Extremal Graph Theory, Combinatorial Number Theory and Theoretical Computer Science. Strong hypergraph extensions of graph regularity techniques were recently given by Nagle, Rödl, Schacht and Skokan, by W.T. Gowers, and subsequently, by T. Tao. These extensions have yielded quite a few non-trivial applications to Extremal Hypergraph Theory, Combinatorial Number Theory and Theoretical Computer Science. A main drawback to the hypergraph regularity techniques above is that they are highly technical. In this thesis, we consider a less technical version of hypergraph regularity which more directly generalizes Szemeredi's regularity lemma for graphs. The tools we discuss won't yield all applications of their stronger relatives, but yield still several applications in extremal hypergraph theory (for so-called linear or simple hypergraphs), including algorithmic ones. This thesis surveys these lighter regularity techiques, and develops three applications of them.