# Any nice packages for word alignment?

I want to visualize word alignments between sentence pairs, where the positions of aligned words may differ between the sentences, and a word in one sentence may be aligned to more than one word in the other, or even have no partner at all.

A picture is worth a thousand words:

Are there any nice packages for that job? If there are no specialized packages, what would be a good alternative?

-
Is this notation used anywhere in linguistics? I've never come across it before, so I suspect there may not be any package for it. (What would be the thousand words that this diagram is showing?) –  Alan Munn Aug 11 '11 at 4:47
It is used in papers about IBM/word-based models. This example is taken from acl.ldc.upenn.edu/J/J90/J90-2002.pdf –  danlei Aug 11 '11 at 4:53
I see. Thanks. I think you would have to roll your own methods then. I would suggest TikZ. There are some TikZ wizards here that might have some ideas. Are you going to be making a lot of these diagrams, or just the occasional one? If the latter, then doing each one by hand wouldn't be too bad; if a lot, ideally you'd want automatically split the sentences and create the relevant nodes to be connected. –  Alan Munn Aug 11 '11 at 5:07
It's for a term paper about SMT, in which I will contrast the approach of the paper I linked above with more recent methods (e.g. phrase-based SMT), and include a few more detailed explanations from Koehn's SMT book. So it's the occasional one. Do you know about anything that produces roughly similar output, so I wouldn't have to do it by hand? (I'm absolutely no TeX expert, and I don't want to spend too much time for just this one graphic) –  danlei Aug 11 '11 at 5:29
Oh, and thank you for the help so far. Usually, I'd be willing to spend more time with this, but at the moment I want to focus on the content rather than my TeX skills, since the paper is due in two days. –  danlei Aug 11 '11 at 5:41

\documentclass{article}
\usepackage{pst-node}
\def\W#1#2{\rnode{#1}{#2}\hfill}
\begin{document}

\W{a}{The} \W{b}{proposal} \W{c}{will} \W{d}{not} \W{e}{now} \W{f}{be} \W{g}{implemented}

\vspace{4cm}
\W{A}{Les} \W{B}{propositions} \W{C}{nes} \W{D}{seront} \W{E}{pas} \W{F}{mises} \W{G}{en}
\W{H}{application} \W{I}{maintenant}
\psset{nodesep=5pt}
\ncline{a}{A}\ncline{b}{B}
\ncline{c}{D}
\ncdiag[border=4pt,angleA=-90,angleB=90,arm=5mm]{d}{C}
\ncput[npos=1.5]{\rnode{dC}{}}
\ncdiag[nodesepA=0pt,armB=5mm,angleA=-55,angleB=90]{dC}{E}
\ncdiag[angleA=-90,angleB=90,arm=5mm]{e}{I}
\ncdiag[border=4pt,angleA=-90,angleB=90,arm=5mm]{g}{F}
\ncput[npos=1.8]{\rnode{gF}{}}
\ncdiag[nodesepA=0pt,armB=5mm,angleA=-75,angleB=90]{gF}{G}
\ncdiag[nodesepA=0pt,armB=5mm,angleA=-20,angleB=90]{gF}{H}
\ncdiagg[angleA=-90,angleB=90,nodesepB=7mm]{f}{f}

\end{document}


-
This one comes closest to the original, thanks. –  danlei Aug 11 '11 at 18:19

Ok, here's a quick and dirty TiKZ solution. I haven't connected be in the diagram, although I assume it actually should be connected with seront. If you want to connect them, you could make a p3 node below now in the matrix and connect will and be to that and then connect that to seront.

Update I've tweaked a few parameters to make the spacing between the words better.

\documentclass{article}
\usepackage[margin=1in]{geometry}
\usepackage{tikz}
\usetikzlibrary{intersections,positioning}
\newcommand*{\hnode}[1]{\node[outer sep=0pt,anchor=base] (#1) {#1};} % create a labelled node
\begin{document}

\begin{tikzpicture}
% First make a matrix containing as many columns as the longest sentence.
% Each cell contains a node whose label is identical to the word itself
\matrix[column sep=0em,row sep=.4in] {
% First sentence
\hnode{The} & \hnode{proposal} & \hnode{will} & \hnode{not} & \hnode{now} & \hnode{be} &  \hnode{implemented}  &\\
% Now create some dummy nodes to make intermediate nodes
& & & \node[inner sep={0pt},minimum width=0pt] (p1) {}; & & & \node[inner sep={0pt},minimum width=0pt] (p2) {};\\
% Second sentence
\hnode{Les} & \hnode{propositions} & \hnode{ne}  & \hnode{seront} & \hnode{pas} & \hnode{mises} & \hnode{en} & \hnode{application} & \hnode{maintenant}\\
};
% Now connect the nodes.  For paths that we want to break, name the path
\draw (The) -- (Les);
\draw (proposal) -- (propositions);
\draw[name path=willP] (will) -- (seront.north);
\draw (not) -- (p1);
\path[name path=neP] (p1) -- (ne);
\draw (p1) -- (pas);
\draw[name path=nowP] (now.south)  -- (maintenant.north);
\path[name path=impP] (implemented) -- (p2);
\draw (p2) -- (mises.north);
\draw (p2) -- (en);
\draw (p2) -- (application.north);
% Now break the paths at the intersection by drawing a white circle over it
\fill[white, name intersections={of=willP and neP}] (intersection-1) circle (4pt);
\fill[white, name intersections={of=nowP and impP}] (intersection-1) circle (4pt);
% Finally redraw the path you don't want broken
% Is there a more elegant way to do this?
\draw (p1) -- (ne);
\draw (implemented) -- (p2);
\end{tikzpicture}

\end{document}


-
Thank you very much! (I'll wait with accepting a few hours) –  danlei Aug 11 '11 at 6:35
Great answer, Alan! =) –  Paulo Cereda Aug 11 '11 at 10:35
This time it was hard to choose what I should accept. Herbert's came closer to the original, but yours was very helpful, too. About the connection to seront: You're right, they should be connected, but this is a weakness in the early IBM models -- "it does not allow several source words to work together to produce a single target word." (See the "Plans" section in the linked paper) –  danlei Aug 11 '11 at 18:35

This is building on Alan's answer, getting it to work with my answer to Is there a TikZ equivalent to the PSTricks \ncdiag command?

Here's the code:

\documentclass{article}
%\url{http://tex.stackexchange.com/q/25474/86}
\usepackage{tikz}
\usetikzlibrary{calc,matrix}
\newcommand{\hnode}[1]{|(#1)| #1}

\tikzset{
arm angleA/.initial={0},
arm angleB/.initial={0},
arm lengthA/.initial={0mm},
arm lengthB/.initial={0mm},
arm length/.style={%
arm lengthA=#1,
arm lengthB=#1,
},
arm/.style={
to path={%
(\tikztostart) -- ++(\pgfkeysvalueof{/tikz/arm angleA}:\pgfkeysvalueof{/tikz/arm lengthA}) -- ($(\tikztotarget)+(\pgfkeysvalueof{/tikz/arm angleB}:\pgfkeysvalueof{/tikz/arm lengthB})$) -- (\tikztotarget)
}
},
}

\begin{document}

\begin{tikzpicture}
\matrix[column sep=0em,row sep=.4in,matrix of nodes,row 2/.style={coordinate}] (m) {
% First sentence
\hnode{The} & \hnode{proposal} & \hnode{will} & \hnode{not} & \hnode{now} & \hnode{be} &  \hnode{implemented}  &\\
% Now create some dummy nodes to make intermediate nodes
& & &|(p1)| {} & & &|(p2)| {}\\
% Second sentence
\hnode{Les} & \hnode{propositions} & \hnode{ne}  & \hnode{seront} & \hnode{pas} & \hnode{mises} & \hnode{en} & \hnode{application} & \hnode{maintenant}\\
};
% Now connect the nodes.
\begin{scope}[every path/.style={line width=4pt,white,double=black},every to/.style={arm}, arm angleA=-90, arm angleB=90, arm length=5mm]
\draw (The) to (Les);
\draw (proposal) to (propositions);
\draw (will) to (seront);
\draw (not) to[arm lengthB=0pt] (p1)
(p1) to[arm lengthA=0pt] (ne)
(p1) to[arm lengthA=0pt] (pas);
\draw (now) to (maintenant);
\draw (be) -- ++(0,-.2in);
\draw (implemented) to[arm lengthB=0pt] (p2)
(p2) to[arm lengthA=0pt] (mises)
(p2) to[arm lengthA=0pt] (en)
(p2) to[arm lengthA=0pt] (application);
\end{scope}
\end{tikzpicture}

\end{document}


Here's the result:

As well as the arm stuff, we handle the intersections by using the double feature which draws a line twice at two thicknesses. By making the outer one white and the inner one black, we can "slice" out the underlying lines.

(The picture's been a bit zealously cropped ... the "maintenant" is there in the real picture.)

Update: I wasn't happy with the fact that the lines were of different lengths, so I hacked the matrix node style (a lot) so that the rows would expand to some length. We measure the length of the French sentence and then tell the English one to expand to the same amount. This is a bit nicer to look at, I reckon; though the price to pay might be a little high!

And now the code:

\documentclass{standalone}
%\url{http://tex.stackexchange.com/q/25474/86}
\usepackage[scale=.95]{geometry}
\usepackage{tikz}
\usetikzlibrary{calc,matrix}
\newcommand{\hnode}[1]{|(#1)| #1}

\makeatletter
\tikzset{
arm angleA/.initial={0},
arm angleB/.initial={0},
arm lengthA/.initial={0mm},
arm lengthB/.initial={0mm},
arm length/.style={%
arm lengthA=#1,
arm lengthB=#1,
},
arm/.style={
to path={%
(\tikztostart) -- ++(\pgfkeysvalueof{/tikz/arm angleA}:\pgfkeysvalueof{/tikz/arm lengthA}) -- ($(\tikztotarget)+(\pgfkeysvalueof{/tikz/arm angleB}:\pgfkeysvalueof{/tikz/arm lengthB})$) -- (\tikztotarget)
}
},
expand/.code={%
\let\pgf@matrix@compute@origin=\pgf@matrix@compute@origin@expand
\let\pgf@matrix@cont=\pgf@matrix@cont@expand%
\let\pgf@matrix@cell@cont=\pgf@matrix@cell@cont@expand
},
expand width/.initial={100pt},
}

\def\ex@minwidth{100pt}%
\let\pgf@matrix@compute@origin@orig=\pgf@matrix@compute@origin
\def\pgf@matrix@compute@origin@expand{%
\pgf@matrix@compute@origin@orig
\pgfmathsetmacro{\ex@width}{%
\csname pgf@matrix@minx\the\pgf@matrix@numberofcolumns\endcsname -
\csname pgf@matrix@minx1\endcsname +
\csname pgf@matrix@maxx\the\pgf@matrix@numberofcolumns\endcsname +
\csname pgf@matrix@maxx1\endcsname +
2*\pgfkeysvalueof{/pgf/inner xsep}
}
\pgfmathsetmacro{\ex@extra}{max(0,(\pgfkeysvalueof{/tikz/expand width} - \ex@width)/(\pgf@matrix@numberofcolumns - 1))}%
{%
\c@pgf@counta=1\relax%
\loop%
\ifnum\c@pgf@counta<\pgf@matrix@numberofcolumns\relax%
\pgfmathparse{\csname pgf@matrix@minx\the\c@pgf@counta\endcsname + (\c@pgf@counta - 1) * \ex@extra}%
\expandafter\xdef\csname pgf@matrix@minx\the\c@pgf@counta\endcsname{\pgfmathresult pt}%
\repeat%
}%
}
\def\pgf@matrix@cont@expand{%
\setbox\pgf@matrix@box=\hbox\bgroup\vbox\bgroup%
\pgfmathparse{\pgfkeysvalueof{/tikz/expand width} - 2*\pgfkeysvalueof{/pgf/inner xsep}}%
\halign to \pgfmathresult pt\bgroup%
\pgf@matrix@init@row%
\pgf@matrix@step@column%
{%
\pgf@matrix@startcell%
##%
\pgf@matrix@endcell%
}%
\tabskip=0pt\relax
&%
##%
\tabskip=0pt plus 1fil\relax
&%
\pgf@matrix@step@column%
{%
\pgf@matrix@startcell%
##%
\pgf@matrix@endcell%
}%
\tabskip=0pt\relax
&%
\cr%
}

\def\pgf@matrix@cell@cont@expand[#1]{%
\ifnum\pgfmatrixcurrentcolumn<\pgf@matrix@numberofcolumns%
\else%
{%
\global\pgf@matrix@fixedfalse%
\pgf@x=0pt%
\ifpgf@matrix@fixed%
fmatrixcurrentcolumn\endcsname%
{\global\pgf@picmaxx=0pt}%
\fi%
\advance\pgfmatrixcurrentcolumn by1\relax % only temporary for the following:
\expandafter\xdef\csname pgf@matrix@column@sep@\the\pgfmatrixcurrentcolumn\endcsname{\the\pgf@x}%
\ifpgf@matrix@fixed%
\expandafter\gdef\csname pgf@matrix@column@finish@\the\pgfmatrixcurrentcolumn\endcsname{\global\pgf@picminx=0pt}%
\else%
\expandafter\global\expandafter\let\csname pgf@matrix@column@finish@\the\pgfmatrixcurrentcolumn\endcsname=\pgfutil@empty%
\fi%
}%
\fi%
&\pgf@matrix@correct@calltrue&\pgf@matrix@correct@calltrue&%
}%

\makeatother

\begin{document}

\begin{tikzpicture}
% Second sentence
\matrix[column sep=0em,matrix of nodes] (French) {
\hnode{Les} & \hnode{propositions} & \hnode{ne}  & \hnode{seront} & \hnode{pas} & \hnode{mises} & \hnode{en} & \hnode{application} & \hnode{maintenant}\\
};
\path (French.east);
\pgfgetlastxy{\Frrx}{\Frry}%
\path (French.west);
\pgfgetlastxy{\Frlx}{\Frly}%
\pgfmathsetmacro{\Frwidth}{\Frrx - \Frlx}%
\path (French) ++(0,.8in) node[matrix,column sep=0em,matrix of nodes,expand,expand width={\Frwidth pt}] (English) {
% First sentence
\hnode{The} & \hnode{proposal} & \hnode{will} & \hnode{not} & \hnode{now} & \hnode{be} &  \hnode{implemented}\\
};
% Now connect the nodes.
\begin{scope}[every path/.style={line width=4pt,white,double=black},every to/.style={arm}, arm angleA=-90, arm angleB=90, arm length=5mm]
\draw (The) to (Les);
\draw (proposal) to (propositions);
\draw (will) to (seront);
\draw (not) -- ++(0,-.4in) coordinate (p1) {}
(p1) to[arm lengthA=0pt] (ne)
(p1) to[arm lengthA=0pt] (pas);
\draw (now) to (maintenant);
\draw (be) -- ++(0,-.4in);
\draw (implemented) -- ++(0,-.4in) coordinate (p2)
(p2) to[arm lengthA=0pt] (mises)
(p2) to[arm lengthA=0pt] (en)
(p2) to[arm lengthA=0pt] (application);
\end{scope}
\end{tikzpicture}
\end{document}


It really is horrendous hackery the third. Not only do we have to mess around with the node placement in the matrix command, we also have to modify one of the main routines: the \halign that actually places the nodes in the right places. This is because we want to add some stretchable glue between the columns, using \tabskip. Only we don't want it at the edges. I'm not an \halign aficionado but the only way I could get this to work was by introducing another column between each actual column in the matrix (in addition to the extra one already there!) which could handle the alignment. Otherwise, trying to set \tabskip in the \halign preamble meant that either it was in place at the end of the row (not wanted) or wasn't in place between the columns (wanted).

So this is most definitely not recommended, but it was bugging me!

-
You could do \tikzmark's and \hfill similar to what Herbert is doing. Thought that table-hackery could be useful in other situations as well. –  Caramdir Aug 12 '11 at 15:43
@Caramdir: Yes, you could. I was trying to get a TikZ-only version. A simpler solution would be to measure the width on the first run and then use it for positioning on a second run. –  Loop Space Aug 12 '11 at 18:56

Here is an attempt using PStricks:

\documentclass{article}
\usepackage[english]{babel}
\usepackage{pstricks}% http://www.tug.org/PSTricks/main.cgi/
\usepackage{pst-node}
\usepackage{calc}% For width calculations
\begin{document}

\newcommand*{\Tword}[1]{\rnode{#1}{\raisebox{1ex}{\smash{#1}}}}% \Tword{<top>}
\newcommand*{\Bword}[1]{\rnode{#1}{\raisebox{-2ex}{\smash{#1}}}}% \Bword{<bottom>}

\newcommand{\TtoB}[3][]{% \TtoB{<top>}{<bottom}
\ncdiag[arm=1em,angleA=-90,angleB=90,linestyle=solid,linecolor=black,linewidth=0.5pt,#1]{#2}{#3}}%

\begin{pspicture}(10,10)
\rput[l](0,1){% English phrase
\makebox[\widthof{Les propositions ne seront pas mises en application maintenant}][l]{\Tword{The} \Tword{proposal} \Tword{will} \Tword{not} \Tword{now} \Tword{be} \Tword{implemented}}%
}%

\rput[l](0,-1){% French phrase
\Bword{Les} \Bword{propositions} \Bword{ne} \Bword{seront} \Bword{pas} \Bword{mises} \Bword{en} \Bword{application} \Bword{maintenant}%
}%

% Node connections between TOP (English) and BOTTOM (French) phrases
\TtoB{The}{Les}%
\TtoB{proposal}{propositions}%
\TtoB{will}{seront}%
\TtoB[linewidth=5pt,linecolor=white]{not}{ne} \TtoB{not}{ne} \TtoB{not}{pas}%
\TtoB{now}{maintenant}%
\TtoB[linewidth=5pt,linecolor=white]{implemented}{mises}%
\TtoB[linewidth=5pt,linecolor=white]{implemented}{en}%
\TtoB[linewidth=5pt,linecolor=white]{implemented}{application}%
\TtoB{implemented}{mises} \TtoB{implemented}{en} \TtoB{implemented}{application}% Redraw
\end{pspicture}

\end{document}


The overlap between word/node connections is solved by drawing each connection once with white (5pt) and then with black (0.5pt).

Modifying the <position> identifier of the \makebox command from l (left) to c (center) yields:

...and modifying it to s (spread) yields:

Although typeset properly with the correct spread, LaTeX chokes a little on the last definition \makebox[..][s]{...} and complains about Underfull \hbox (badness 10000).

Adding a connection from be to 'nowhere is obtained by

\pcline([nodesep=0pt,angle=-90]be)([nodesep=1em,angle=-90]be)% No translation


so that it matches the arms of \ncdiag (in \TtoB) in length 1em and width 0.5pt downward (angle=-90`).

-