This manual can be displayed by calling just
WordAlign or alternatively
Word alignments in natural languages
This library and program are designed for the alignment of words in human
Implemented with ideas described in:
- Christian Hoener zu Siederdissen
Sneaking Around ConcatMap: Efficient Combinators for Dynamic Programming
2012, Proceedings of the 17th ACM SIGPLAN international conference on Functional programming
- Andrew Farmer, Christian Höner zu Siederdissen, and Andy Gill.
The HERMIT in the stream: fusing stream fusion’s concatMap
2014, Proceedings of the ACM SIGPLAN 2014 workshop on Partial evaluation and program manipulation.
- Christian Höner zu Siederdissen, Ivo L. Hofacker, and Peter F. Stadler.
Product Grammars for Alignment and Folding
2014, IEEE/ACM Transactions on Computational Biology and Bioinformatics. 99
- Christian Höner zu Siederdissen, Sonja J. Prohaska, and Peter F. Stadler
Algebraic Dynamic Programming over General Data Structures
2015, BMC Bioinformatics
Word alignments require three pieces of information: (i) the words to be
aligned, (ii) the selection of an alignment algorithm, and (iii) a scoring
scheme (either simple or bigram-based). Each of these is described below.
Words to be Aligned
Each word is encoded as a list of characters. A single character, however,
is encoded as a list of unicode symbols, not just a single symbol.
This particular encoding is necessary because there is no general one-to-one
mapping of atomic alphabet symbols to unicode characters. Just consider
character decorations, such as Umlaute (even though Umlaute are available in
As user, you send a list to stdin that is formatted as follows (with all fields
mandatory; the tab symbol being the separator between each column):
- word id
- language name
- meaning identifier (this is a string, not a number)
- length of the word
- space-separated characters (each character is actually a string)
(In case you read the plain-text version of this document, the 4 whitespace
characters should be left out.)
0 Albanian_Tosk 1.100 5 \' b o t ə
2 Albanian_Tosk 1.100 10 r̃ o k u lʸ i a\' lʸ e m
Selection of Alignment Algorithm
The WordAlignment program comes with these modes:
||Number of Input Tapes
Mode names can be shortened to unique prefixes.
Global alignments use a NeedlemanWunsch style algorithm with linear gap costs.
Overhang alignments use affine gap scoring. Overhang alignments separate the
alignment into three phases, the prefix, infix, and suffix phase. Typically,
prefix and suffix phases have very low costs.
Common default options
-? --help Display help message
-V --version Print version information
--numeric-version Print just the version number
-v --verbose Loud verbosity
-q --quiet Quiet verbosity
--verbose prints status information every 10.000 alignments
Common options for all alignments variants
--simplescorefile=ITEM the file to read the simple scores from
-l --lpblock=ITEM,ITEM compare ONLY the given pair of languages: i.e
'Breton','Breton' or 2,3 (with the latter
notation '2' being the 2nd language in the input
--showmanual show the manual and quit
--filterscore=NUM only print results with this score or higher
--filterbacktrack=NUM only provide backtracking results for results
with this score or higher
--simplescorefile expects a score file for simple unigram based scoring.
An example file is provided under
scores/defaultSimpleScoring. For bigram
score files, use a file like
--lpblock expects a pair of language names (Breton,Breton) or a pair of
integers (3,3 or 4,6) and will then align only the given language pairs with
each other. This option should be very helpful in case you want to parallelize
--filterscore is used to limit printing results to only the alignments
with score not lower than this option. Given that printing requires a
significant amount of CPU time due to unicode conversion, this option improves
--filterbacktrack is used to limit printing of backtracking for a given
alignment to the best results. Works like
--filterscore but will always
print the forward result.
--filternormalized applies filter on the length-normalized scores instead
of the absolute ones.
Options for bigram alignment variants
-b --bigramscorefile=ITEM the file to read the bigram scores from
--bigramscorefile is used to point toward a file with a list of bigram
scores for all language pairs.
Simple score file description
Bigram score file description
In contrast to the simple model above, however, character matching is now
performed in a bigram context.
The required score file is currently using an in-house format with the
following columns all required (with whitespace, not tab between the entries):
- language name
- character (bigram 1.1)
- character (bigram 1.2)
- language name
- character (bigram 2.1)
- character (bigram 2.2)
Three example lines
Albanian_Tosk \' a Albanian_Tosk \' a 4.25238
Albanian_Tosk \' a Albanian_Tosk \' b 0.402228
Albanian_Tosk \' a Albanian_Tosk \' g 1.07432
The output are four lines for each alignment. An info line with the word ids
(IDS), the alignment score (SCORE), the normalized scores (NSCORE) and the
actual words, started by (WORD) and interleaved by (WORD). The next two lines
are the alignment, with deletions showning up as minus symbols
- in the
deletion field. Note that a deletion does not delete a character from the
input, it merely aligns an existing character in one alignment with the symbol
- in the other. The final line provides the per-column score
for the alignment. After the alignment follows one empty line.
Words are written left-to-right in the information line, and bottom to top in
IDS: 2 3 SCORE: 93.40 NSCORE: 10.38 WORD: ^ h a u s b a u $ WORD: ^ b a u m h a u s $
b a u m h a u s $ - - -
- - - - h a u s b a u $
0.0 0.0 0.0 -1.0 -3.0 33.9 33.8 33.7 -3.0 -1.0 0.0 0.0
Measured on a core i5-3570K @ 3.40 GHz; single-threaded, based on 2001000 alignments.
The program is not compiled for multi-threading, if you need this consider the
--lpblock option first and parallelize on the language pair level.
Otherwise, send a mail.
When aligning short words, as occur in human language, the approximate number
of alignments per second is:
||Alignments per Second
and when printing alignments via
--filterscore is restricted to scores
>=10 to return about 0.6% of alignments:
||Alignments per Second
Three- and Four-way Alignments
These are currently disabled. If you need them, consider contacting me.
Writing unit tests for WordAlign
First, prepare a version of WordAlign that includes the properties test
program. This is done as follows with a sufficiently new version of cabal:
cabal new-configure --enable-tests
Once done, take a look at the
tests folder. The files with suffix
.golden are named in a special manner:
- grammar type
- score system
- the score files used; for unigrams a single
.ugdef file is required,
for bigrams both a
.bgdef and a
.bgms file are required.
.ugdef files hold a unigram scoring system.
.bgdef files bigram
default scores. Last,
.bgms files hold scores for known bigrams.
- the input words file with the words to be aligned to each other. From the
file, all pairs are created where fst <= snd. I.e. the upper triangular
matrix of words.
- a number with the the co-optimals to backtrack. Normally, this should be
1 but a small number of tests should have a big number here -- say
99 and all possible co-optimals should be checked for correctness.
This may be fewer than the given number but at least one backtrack should
always be there.
Running the properties program will then automatically test each golden file vs
the WordAlign algorithm together with the score files as inputs.
Automatic property are done with a simple
./properties and should be all
How to create new test files:
- Create a new empty file named like this example here:
- This will test against the global Needleman-Wunsch algorithm with bigram
scoring. The score file used is the
PTSP800.bgms bigram score file and
PTSP800.bgdef file. Words are taken from the
PTpoSPpampa.words file. Exactly one backtrack is generated.
- Fill the necessary scoring and words files.
- Run the
properties program as follows:
properties --accept -i.
This should fill the previously empty golden file created in step 1.
- Carefully check if the contents of this file are correct.
- If so a run of
./properties should now only show green results. In
particular, the file name created under 1. should show up as a new property
that was tested.
Christian Hoener zu Siederdissen
Leipzig University, Leipzig, Germany