We discuss some examples to show that human text in general, and translations in particular, are difficult.

Human text is unstructured, and replete with ambiguity; often the sense of a (group of) words depends essentially on the context. Here is a list of funny examples.

1. For typos, consider the word occurrence; here are some variations: occurence, occurance, ocurrence.
2. The abbreviation St. can mean Saint or Street: Saint Anthony Hospital may also be written as St. Anthony Hospital. Data normalization is a method to standardize naming in databases.
3. The same meaning can be expressed with different words: The train left at noon., The train departed at twelve o’clock., and At midday the train pulled out of the station. A program that matches on common words sees three unrelated sentences.
4. The same words can carry different meanings. May may arrive in May., I sat on a bank near the river bank., The bass player caught a bass., They lead the expedition that mines lead.
5. One expression can have opposite meanings: It’s a hell of a film., It’s a hell of a mess.
6. One place name can refer to different places: Paris, France and Paris, Texas.
7. One place can have several names: New York, New York City, NYC, or even the Big Apple.
8. A word can change role: Mr. Baker is a baker and lives on Baker Street.
9. Two strings can have exactly the same words, but a different meaning: This is good, not bad at all. or This is bad, not good at all.¹⁰¹⁰This example is taken from Bishop and Bishop, Deep Learning: Foundations and Concepts.
10. Finally, it is surprisingly hard to say where a sentence ends: Dr. P.A.M. Smith Sr. arrived at 2 p.m. When he met a friend, Prof. H. Jones, M.D., Ph.D., at the Mass. Inst. of Tech., he said: “Hi, Dr. Jones! How are you?”.

So, even before we start matching translations, we see that ordinary text defeats many simple rules for automatic matching and parsing. For decades, people have used tools based on regular expressions such as grep.¹¹¹¹Related tools include awk, sed, perl, and python. These tools are extremely useful when the pattern is clear, but they can fail badly when the meaning depends on context.¹²¹²Interestingly, ChatGPT and Claude are very good at using such tools. In general, manually designed text-processing rules, such as rules for search and replace, are fragile, even when they look reasonable at first.

All in all, whenever you later have to work on human text, we want you to remember from these examples: text analysis is full of pitfalls, and `home-brewed’ rules are usually naive, and often wrong altogether.

Translation adds another layer of difficulty. At the word level, names change spelling across languages: Gretel versus Grethel in the fairy tale. Next, translators may replace an explicit name by a description. In Hansel and Grethel, the source may say that Hansel stooped down, while the translation says that the boy stooped down; the reader has to infer that the boy is Hansel. A source may first describe the children as a boy and a girl, while a translation may describe them as the elder and the younger. Consequently, exact word matching is too brittle to use directly for matching translations.

At the sentence level, translators split, merge, and rewrite. This means that sentence \(i\) in the source need not correspond exactly to sentence \(i\) in the target. To illustrate, here is a French version of the first sentence of Les Mille et Une Nuits¹³¹³Wikipedia: Les Mille et Une Nuits. compared with three English translations and one by ChatGPT. Notice how each human translator restructures the sentence differently, and adds or removes material. Interestingly, the translation offered by ChatGPT is nearly literal.

Les chroniques des Sassaniens, anciens rois de Perse, qui avaient étendu leur empire dans les Indes, dans les grandes et petites îles qui en dépendent, et bien loin au delà du Gange jusqu’à la Chine, rapportent qu’il y avait autrefois un roi de cette puissante maison, qui était le plus excellent prince de son temps. —A. Galland

The chronicles of the Sassanids, the ancient kings of Persia, who had extended their empire into India, across the large and small islands belonging to it, and far beyond the Ganges as far as China, relate that there once lived a king of that powerful dynasty who was the most excellent prince of his time. —ChatGPT 5.6¹⁴¹⁴This translation was produced without special instructions.

In the chronicles of the ancient dynasty of the Sassanidae, who reigned for about four hundred years, from Persia to the borders of China, beyond the great river Ganges itself, we read the praises of one of the kings of this race, who was said to be the best monarch of his time. —A. Lang

It is related (but God alone is all-knowing, as well as all-wise, and almighty, and all-bountiful,) that there was, in ancient times, a King of the countries of India and China, possessing numerous troops, and guards, and servants, and domestic dependents: and he had two sons; one of whom was a man of mature age; and the other, a youth. —E.W. Lane

Therein it is related (but Allah is All knowing of His hidden things and All ruling and All honored and All giving and All gracious and All merciful) that, in tide of yore and in time long gone before, there was a King of the Kings of the Banu Sásán in the Islands of India and China, a Lord of armies and guards and servants and dependents. —R.F. Burton

At a higher level yet, translators sometimes leave out sentences, or even entire paragraphs. They might split paragraphs of the source into several target paragraphs, or merge paragraphs of the source into one paragraph in the target. And finally, the splits and merges they introduce might be in the middle of a paragraph, that is, they do not respect the boundaries of the source paragraphs at all.

This is why we should not try to find a perfect match by exact rules. Instead, we look for a matching with a low total loss, so that the alignment works well in most places. We compare chunks of text by features, such as names, punctuation, length, and other markers, and allow the matching algorithm to skip, split, and merge chunks when that gives a better overall alignment. The next section formalizes this idea.

Now that we have some understanding of the complications that arise in matchmaking, we discuss the concept of dynamic programming and then model text matching in this framework.

A dynamic programming problem in discrete time with time horizon \(N\) contains the following elements.¹⁵¹⁵Bertsekas, A Course in Reinforcement Learning, 2026. The variable \(x_k\) represents the state of the system at time \(k\).¹⁶¹⁶In this section we follow the notation that is standard in the dynamic-programming literature: \(x\) is a state. In later sections, \(x\) denotes a feature vector. The state space is the set of all possible states. A control variable¹⁷¹⁷Also called action. \(u_k\) modifies the state through the function \(T_k(x_k, u_k)\) to produce the state at the next time moment

\begin{align*} x_{k+1} = T_{k}(x_{k}, u_{k}). \end{align*}

The control \(u\) lies in a control set \(U(x)\) that depends on the state \(x\). Finally, the function \(g(x,u)\) specifies the running cost¹⁸¹⁸Or one-step cost or reward. of exercising control \(u\) in state \(x\), and \(g_N\) is the terminal cost.

Let us illustrate this with a single-item inventory model. The state \(x_k\) is the number of items in stock at the end of period \(k\). We assume we can order any amount we like so \(U(x) = \set{0, 1, \ldots}\). If we order \(Q\) units as soon as the inventory drops to or below the reorder level \(r\), then \(u_k = Q \1{x_k \leq r}\). Then, with \(d\) the constant demand per period,

\begin{align*} x_{k+1} &= T_k(x_k, u_k) = x_k - d + u_k. \end{align*}

If placing an order costs ordering cost \(K\) and the function \(h(x)\geq 0\) represents the inventory cost, then \(g(x,u) = h(x) + K \1{u \geq 1}\). If we finish after \(N\) periods, we set the cost \(g_N\) to zero.

As the evolution is deterministic, the entire state trajectory \(x_1,x_2,\ldots,x_N\) is determined by the starting state \(x_1\), the sequence of controls \(u_1,u_2,\ldots,u_{N-1}\), and the rule \(x_{k+1}=T_k(x_k,u_k)\). The total cost of this trajectory is

\begin{align*} J(x_{1}; u_{1}, u_{2}, \ldots, u_{N-1}) = g_{N}(x_N) + \sum_{k=1}^{N-1} g_k(x_k, u_{k}), \end{align*}

where \(g_N\) is the terminal cost.

The value function \(J_k^*(x)\) is the minimum remaining cost from state \(x\) at time \(k\), optimized over all future controls:

\begin{align*} J^{*}(x) = \min_{u\in U} J(x; u), \end{align*}

where \(U=(U_1, U_2, \ldots, U_N\) and \(u=(u_1, u_2, \ldots, u_N)\). It can be proven¹⁹¹⁹See the many books of Bertsekas on dynamic programming. that the value functions satisfy the dynamic programming equations (DPE):²⁰²⁰Also called Bellman equations.

\begin{align*} J^{*}_{N}(x_{N}) &= g_{N}(x_{N}), \\ u^{*}_{k}(x_{k}) &\in \argmin_{u_{k} \in U_{k}(x_{k})} \set{g_k(x_{k}, u_{k}) + J^{*}_{k+1}(T_{k}(x_{k}, u_{k}))}, \\ J^{*}_{k}(x_{k}) &= \min_{u_{k} \in U_{k}(x_{k})} \set{g_k(x_{k}, u_{k}) + J^{*}_{k+1}(T_{k}(x_{k}, u_{k}))} \\ &= g_k(x_{k}, u_{k}^{*}) + J^{*}_{k+1}(T_{k}(x_{k}, u_{k}^{*})). \end{align*}

The first equation is the terminal condition; the second provides the optimal control; the third is the backward recursion; the fourth follows from the second. In essence, dynamic programming combines recurrence and optimization: if we know \(J^{*}_{k+1}\) we can optimize to find \(J^{*}_{k}\).

The DP code is recursive, and understanding recursion takes some getting used to. To help you practice with this way of thinking, we first discuss a few algorithms that are very elegant, but also very useful to know and understand.²¹²¹The trees we discuss later are also defined recursively.

Two famous recursive algorithms are Quicksort and the K-median. Quicksort takes a list and returns its elements in increasing order. K-Median takes a list and a number \(k\), and returns the element that would stand at position \(k\) if the list were sorted; \(k\) is called the rank of that element. Since the element halfway the sorted list is a median, we obtain a median of an unsorted list of \(n\) elements by asking for the element of rank \(\lceil n/2 \rceil\).

Both algorithms reduce a question about a list \(\Sset\) to the same question about shorter lists. For this the pivot \(p\) of Alg. 2.3.1 is used to split \(\Sset\) into a set \(\Lset\) with the elements smaller than \(p\), \(\Mset\) with elements equal to \(p\), and \(\Rset\) with elements larger than \(p\). Taking \(p\) from \(\Sset\) itself ensures that the part equal to \(p\) is not empty, hence that the other two parts are both shorter than \(\Sset\), so the recursion reaches a list of at most one element. We take \(p\) uniformly at random, so that no particular input, a sorted list for instance, makes the split lopsided time and again.

\begin{algorithm}
\caption{Choose a pivot uniformly from a finite set.}
\begin{algorithmic}
\State \textbf{Input:} a non-empty finite set $\Sset$.
\State \textbf{Output:} an element of $\Sset$.
\Procedure{ChoosePivot}{$\Sset$}
    \Return $\pr{RandomElement}(\Sset)$
\EndProcedure
\end{algorithmic}
\end{algorithm}

\pr{QuickSort} sorts the part below \(p\) and the part above \(p\) by the same procedure; the part equal to \(p\) needs no sorting, Alg. 2.3.2. Every element of the first part is smaller than every element of the second, and likewise for the second and the third, so the concatenation of the three sorted parts is sorted.²²²²For lists \(u\) and \(v\), the list \(u + v\) consists of the elements of \(u\) followed by the elements of \(v\).

\begin{algorithm}
\caption{Sort a list \(\Sset\) in increasing order.}
\begin{algorithmic}[1]
\State \textbf{Input:} a list $\Sset$.
\State \textbf{Output:} the elements of $\Sset$ in increasing order.
\Procedure{QuickSort}{$\Sset$}
    \If{$|\Sset| \leq 1$}
        \Return $\Sset$
    \EndIf
    \State $p \gets \pr{ChoosePivot}(\Sset)$
    \State $\Lset \gets \qb{x \in \Sset : x < p}$
    \State $\Mset \gets \qb{x \in \Sset : x = p}$
    \State $\Rset \gets \qb{x \in \Sset : x > p}$
    \Return $\pr{QuickSort}(\Lset) + \Mset + \pr{QuickSort}(\Rset)$
\EndProcedure
\end{algorithmic}
\end{algorithm}

The K-median finds the element of rank \(k\) without sorting \(\Sset\). After splitting \(\Sset\) with a pivot \(p\) as in Quicksort, the elements of \(\Lset\) take the ranks \(1,\ldots,|\Lset|\), the copies of \(p\) take the ranks \(|\Lset|+1,\ldots,|\Lset|+|\Mset|\), and the elements of \(\Rset\) take the ranks above that. Comparing \(k\) with \(|\Lset|\) and \(|\Lset| + |\Mset|\) therefore tells us in which part the element of rank \(k\) lies, without looking at the parts themselves. If \(k\leq \Lset\), its rank there is again \(k\). If instead \(k \leq |\Lset| + |\Mset|\), it is \(p\), and we are done. If it lies in \(\Rset\), the \(|\Lset| + |\Mset|\) elements that precede \(\Rset\) can be discarded because all these elements are smaller than the \(k\)th, so the rank we search for drops to \(k - |\Lset| - |\Mset|\).

\begin{algorithm}
\caption{Find the element of rank \(k\) of a list \(\Sset\).}
\begin{algorithmic}[1]
\State \textbf{Input:} a non-empty list $\Sset$ and a rank $k$.
\State \textbf{Output:} the element of $\Sset$ with rank $k$ when $\Sset$ is sorted increasingly.
\Procedure{KMedian}{$\Sset, k$}
    \State $p \gets \pr{ChoosePivot}(\Sset)$
    \State $\Lset \gets \qb{x \in \Sset : x < p}$
    \State $\Mset \gets \qb{x \in \Sset : x = p}$
    \State $\Rset \gets \qb{x \in \Sset : x > p}$
    \If{$k \leq |\Lset|$}
        \Return $\pr{KMedian}(\Lset, k)$
    \EndIf
    \If{$k \leq |\Lset| + |\Mset|$}
        \Return $p$
    \EndIf
    \Return $\pr{KMedian}(\Rset, k - |\Lset| - |\Mset|)$
\EndProcedure
\end{algorithmic}
\end{algorithm}

The median of a set can now be efficiently computed too. Alg. 2.3.4 computes the median of a list: the rank \(\lceil |\Sset|/2\rceil\) is, for a list of even length, that of the lower of the two middle elements. This is why the output is a median rather than the median.

\begin{algorithm}
\caption{Compute a median of a list \(\Sset\).}
\begin{algorithmic}
\State \textbf{Input:} a non-empty list $\Sset$.
\State \textbf{Output:} a median of $\Sset$.
\Procedure{Median}{$\Sset$}
    \Return $\pr{KMedian}(\Sset, \lceil |\Sset|/2 \rceil)$
\EndProcedure
\end{algorithmic}
\end{algorithm}

The shortest path problem is to find the shortest path from a set of nodes \(\Nset\) to a target \(t\in \Nset\) where the cost is \(c(i,j) \geq 0\) for every arc \((i,j) \in \edges\). We assume that the graph is directed and has cycles.²³²³If there can be cycles, then we need some more advanced algorithms.

For the DPE, the state is the node we stand on, the controls in state \(i\) are the arcs leaving \(i\), the running cost of an arc is \(c(i,j)\), and the terminal cost at \(t\) is zero. With \(J^*(i)\) the cost of a cheapest path from \(i\) to \(t\), the DPE reads \[ J^*(t) = 0, \quad J^*(i) = \min_{j : (i,j) \in \edges} \left\{ c(i,j) + J^*(j) \right\}. \]

The recursion of Alg. 2.3.5 follows this equation directly: to know \(J^*(i)\) we need \(J^*(j)\) for every node \(j\) that \(i\) points to. One point needs care. A node \(j\) can be pointed to by many nodes \(i\), so a plain recursion computes \(J^*(j)\) again for each of them. To prevent recomputing \(J^*(j)\) time and again, we store it as soon as it is known:²⁴²⁴Storing the value of a procedure that has already been called on the same input is called caching or memoization. It is crucially important in recursive procedures. the procedure keeps the set \(\var{seen\_nodes}\) and the map \(J^*\), and returns the stored value at once when the node lies in the set.

\begin{algorithm}
\caption{Cost of a cheapest path from node \(i\) to the target \(t\).}
\begin{algorithmic}[1]
\State \textbf{Input:} a node $i$.
\State \textbf{Output:} the cost $J^*(i)$ of a cheapest path from $i$ to $t$.
\Procedure{ShortestPath}{$i$}
    \If{$i \in \var{seen\_nodes}$}
        \Return $J^*(i)$
    \EndIf
    \If{$i = t$}
        \State $J^*(i) \gets 0$
        \State $\var{seen\_nodes}.\pr{Add}(i)$
        \Return $J^*(i)$
    \EndIf
    \State $\var{best\_cost} \gets \infty$
    \State $\var{best\_next} \gets \cn{None}$
    \For{$j$ such that $(i,j) \in \edges$}
        \State $\var{cost} \gets c(i,j) + \pr{ShortestPath}(j)$
        \If{$\var{cost} < \var{best\_cost}$}
            \State $\var{best\_cost} \gets \var{cost}$
            \State $\var{best\_next} \gets j$
        \EndIf
    \EndFor
    \State $J^*(i) \gets \var{best\_cost}$
    \State $u^*(i) \gets \var{best\_next}$
    \State $\var{seen\_nodes}.\pr{Add}(i)$
    \Return $J^*(i)$
\EndProcedure
\end{algorithmic}
\end{algorithm}

In the travelling salesman problem (TSP) we are given \(n\) cities and a cost \(c(i,j)\) of travelling from city \(i\) to city \(j\), and we look for a tour that starts at city \(1\), visits every city once, and returns to city \(1\) at minimal total cost. The city we stand in is not enough to decide how to continue: where we should go next also depends on which cities we still have to visit. The state is therefore the pair \((i, \Vset)\), with \(i\) the current city and \(\Vset\) the set of cities not yet visited. The controls in this state are the cities \(j \in \Vset\), the running cost of going to \(j\) is \(c(i,j)\), and the next state is \((j, \Vset \setminus \set{j})\). Writing \(J^*(i,\Vset)\) for the cost of a cheapest route from \(i\) back to city \(1\) that visits all of \(\Vset\) on the way, the DPE is \[ J^*(i,\varnothing) = c(i,1), \quad J^*(i, \Vset) = \min_{j \in \Vset} \left\{ c(i,j) + J^*(j, \Vset \setminus \set{j}) \right\}, \] and the cost of a cheapest tour is \(J^*(1, \set{2,\ldots,n})\), see Alg. 2.3.6.

\begin{algorithm}
\caption{Cost of a cheapest tour through \(n\) cities.}
\begin{algorithmic}[1]
\State \textbf{Input:} the current city $i$ and the set $\Vset$ of cities still to visit.
\State \textbf{Output:} the cost $J^*(i,\Vset)$ of a cheapest route from $i$ to city $1$ visiting all of $\Vset$.
\Procedure{Tsp}{$i, \Vset$}
    \If{$(i,\Vset) \in \var{seen\_states}$}
        \Return $J^*(i,\Vset)$
    \EndIf
    \If{$\Vset = \varnothing$}
        \State $J^*(i,\Vset) \gets c(i,1)$
        \State $\var{seen\_states}.\pr{Add}((i,\Vset))$
        \Return $J^*(i,\Vset)$
    \EndIf
    \State $\var{best\_cost} \gets \infty$
    \State $\var{best\_next} \gets \cn{None}$
    \For{$j \in \Vset$}
        \State $\var{cost} \gets c(i,j) + \pr{Tsp}(j, \Vset \setminus \set{j})$
        \If{$\var{cost} < \var{best\_cost}$}
            \State $\var{best\_cost} \gets \var{cost}$
            \State $\var{best\_next} \gets j$
        \EndIf
    \EndFor
    \State $J^*(i,\Vset) \gets \var{best\_cost}$
    \State $u^*(i,\Vset) \gets \var{best\_next}$
    \State $\var{seen\_states}.\pr{Add}((i,\Vset))$
    \Return $J^*(i,\Vset)$
\EndProcedure
\end{algorithmic}
\end{algorithm}

\pr{Tsp} shows that solving the problem by brute force, that is, by computing the cost of every tour and keeping the cheapest, is not the way to go. There are \((n-1)!\) tours, against \((n-1)2^{n-1}\) states,²⁵²⁵The first element of the states runs over all states \(i\) except \(t\), and the second element over all possible sets that do not include the city \(i\) when we are at city \(i\). and \(59!\) is about \(10^{80}\) while \(59 \cdot 2^{59}\) is about \(3 \cdot 10^{19}\). The DP is faster because the cost to go from \((i,\Vset)\) depends on the set of cities already visited, not on the order in which they were visited, so all \((n-1-|\Vset|)!\) orders that arrive at \((i,\Vset)\) share one stored value. That cache, however, holds one number per state, so the time we save is paid for in memory: at \(n=30\) the map \(J^*\) already has more than \(10^{10}\) entries. Brute force fails on time, the DP fails on memory, and neither settles for \(n=60\). In other words: we need heuristics to solve problems that are serious,²⁶²⁶That is, not toy problems. and, as we will see, not only for the TSP, but much more generally.

Now that you practiced with recursion, we can continue with the DP for text sequencing.

Before we can formulate the text matching problem in the above DP terms²⁷²⁷States, control, cost., we need some definitions. A text is a list of elements \((e_{1}, e_2, \ldots, e_{n})\). In our example, the elements are the sentences that make up the text. A chunk is a contiguous subsequence of elements \((e_a, e_{a+1}, \ldots, e_b)\). When \(a=b\) the chunk is a single element, and when \(b<a\) the chunk is empty.

Features are numerical text markers that help describe an element. They can count words or punctuation marks, record the occurrence of names, or indicate the presence of distinctive objects or animals. For each element \(e\), we compute a feature vector \(f(e)=(f_1(e),\ldots,f_p(e))\), where each component corresponds to one selected marker.

In practice, it works best to tune the features iteratively.²⁸²⁸As said, engineering hyperparameters is standard in such problems.

1. Start with a few simple features, such as some names and the number of question marks.
2. Let the computer use the DP below to make a match.
3. Where the match goes wrong, look for more descriptive keywords and add these as features.
4. Run the matcher again with the augmented list, and repeat.

Casting the text matching problem in the form of a DP requires us to formulate a state \(x\), the update function \(T_k\), the control sets \(U_k\), and the cost functions \(g_k\).

We have a left text \(L\), in French say, and a right text \(R\), in English.²⁹²⁹Each is assumed to be a list of sentences obtained by splitting the source text. We write \(|L|\) and \(|R|\) for the lengths of the texts, that is, for the number of elements each contains. The state \(x=(\ell,r)\) points to the first element of each text that has not yet been matched, so \(1 \leq \ell \leq |L|+1\) and \(1 \leq r \leq |R|+1\). The value \(\ell=|L|+1\) means that the left text is used up, and \((|L|+1,|R|+1)\) is the terminal state.

A control \(u\) is the matching of elements of the left and right text into chunks. We can match one element of either side to 0 or more elements of the other side. Matching one element to more than \(\var{MAX\_MATCH}\) elements of the other side seems so implausible that we prevent it.³⁰³⁰This is a hyperparameter, whose value we set from our understanding of the problem. We take \(\var{MAX\_MATCH}=4\). To illustrate, if \(u=(2,1)\) and \(x=(\ell,r)\), then we match the chunk of elements \((\ell, \ell+1)\) of the left text with the single element \((r, r)\) of the right text. The next state becomes

\begin{align*} T(x, u) = T((\ell,r), (i,j)) = (\ell+i, r+j). \end{align*}

We restrict the controls so that exactly one left element is matched with several right elements, or exactly one right element with several left elements; a matching of several with several is not allowed.³¹³¹This is a modeling choice rather than a necessity. It keeps the number of controls in a state proportional to \(\var{MAX\_MATCH}\), and a genuine many-to-many correspondence can still be approximated by two consecutive matches. The price is that a merge-and-resplit of the kind described in Section 2.1 cannot be represented in a single step. We write \(U_L(x)\) for the controls that advance the left text by exactly one element, that is, those that match the left element \(\ell\) with the elements of the right text that follow position \(r\). Then, with \(x=(\ell,r)\),

\begin{align*} U_L(x) &=\begin{cases} \set{(1, j) : 0 \leq j \leq \min\{\var{MAX\_MATCH}, |R|+1-r\}} \text{ if } \ell \leq |L|,\\ \varnothing \text{ if } \ell = |L|+1. \end{cases} \end{align*}

The minimum with \(|R|+1-r\) prevents the match from running past the end of the right text, and the condition \(\ell \leq |L|\) says that there has to be a left element to match at all. The lower limit \(j=0\) matters. The control \((1,0)\) matches the left element \(\ell\) with an empty chunk on the right, and this is how the model represents an element that the translator dropped. Such a move is not free: its cost compares the features of the left chunk with the zero vector, so the matcher pays the full feature mass of the skipped element. Skipping is therefore always charged, and the matcher will only do it when every alternative is worse. Likewise,

\begin{align*} U_R(x) &=\begin{cases} \set{(i, 1) : 0 \leq i \leq \min\{\var{MAX\_MATCH}, |L|+1-\ell\}} \text{ if } r \leq |R|,\\ \varnothing \text{ if } r = |R|+1. \end{cases} \end{align*}

Therefore, the control set is

\begin{align*} U(x) = U_L(x) \cup U_R(x). \end{align*}

The running cost is based on the features of the chunks that make up the match controlled by \(u\). The cost of a match should express how much the chunks of each text resemble each other.³²³²Recall, we match chunks, because there may not be a one-to-one correspondence, due to splitting, merging, or discarding, between the elements of the left and the right text. For each chunk we add up, for each feature separately, the values over all its elements. For example, consider the English chunk The dog chased the cat. The cat ran away. and the features cat, dog, and mouse. The first sentence contributes \([1,1,0]\), and the second contributes \([1,0,0]\), so the chunk feature vector is \([2,1,0]\). If the corresponding French chunk is Le chien a poursuivi le chat., and the French features are chat, chien, and souris, then its feature vector is \([1,1,0]\). More generally, let \(F_L(a,b)\) be the feature vector of the chunk starting at position \(a\) of the left text up to and including element \(b\); similarly \(F_R(c,d)\) is the feature vector of the right chunk for the right elements \([c, \ldots, d]\).

For the cost we take the absolute value of the difference of the features. Clearly, some features may be more important than others, which we achieve by multiplying the contribution of the \(j\)th feature by a weight \(w_j>0\). If \(T((\ell,r),u)=(\ell',r')\), then \[ g((\ell,r),u) = \sum_{j=1}^{p} w_j \left|F_{L,j}(\ell,\ell'-1) - F_{R,j}(r,r'-1)\right|. \]

Observe that \(g\) is still a function of the state and the control. The functions \(F_L\) and \(F_R\) lift these to a feature space. The optimizer never sees the text itself. If we add or remove features, we only have to modify \(F_L\) and \(F_R\); the DP needs no change.

Observe that this problem needs no index \(k\) to track time. Each control advances at least one of the two positions, so the state \((\ell,r)\) can never return to an earlier value, in other words, the position in the two texts is the time index.

Reinforcement Learning starts from the exact DP formulation³³³³Bertsekas, A Course in Reinforcement Learning, 2026, and the references therein for further discussion. above, but the differences are profound. Exact DP assumes that the state is known, that \(U(x)\) can be enumerated, and that the value function \(J^*(x)\) can be computed for all relevant states in the state space. These assumptions do not hold in most problems of practical relevance. The state space may be too large, the control space may be too large to search exhaustively, or the state may be only partly observed. In Markov decision processes there are additional difficulties: the next state and the one-step cost, or reward, are random. The dynamic programming equation then contains an expectation over these random quantities. We do not pursue these concepts further here.

The above gives a mathematical description of the matching problem. For actual computations, however, we need code. Here we specify the ideas in pseudocode. We implement the above model with the \(\cl{Text}\) class and the \(\cl{TextDP}\) class.

The text class in Alg. 2.5.1 receives the elements of a text in one language and the names of the features that matter in that language, such as [ cat, dog, mouse ] in English and [ chat, chien, souris ] in French. Upon initialization of the class, it computes the feature matrix \(F\), where the \(i\)th row \(F_i\) is the feature vector of element \(i\).

\begin{algorithm}
\caption{A Text object.}
\begin{algorithmic}
\State \textbf{Input:} a list $\var{elements}$ and a list of feature names.
\State \textbf{Output:} a text object.
\State \textbf{class } $\cl{Text}(\var{elements}, \var{features})$
\State $\quad$ \textbf{instance variables:}
\State $\quad\quad F \gets \pr{ComputeFeatureMatrix}()$ \Comment{Initialize the feature matrix.}
\State $\quad$ \textbf{methods:}
\State $\quad\quad \pr{ElementFeatures}(\var{element})$ \Comment{Compute features for an element.}
\State $\quad\quad \pr{ComputeFeatureMatrix}()$
\State $\quad\quad \pr{ChunkFeatures}(a,b)$ \Comment{Add up the features in a chunk.}
\end{algorithmic}
\end{algorithm}

The procedure \pr{Text.ElementFeatures}, Alg. 2.5.2, computes one row of the feature matrix \(F\). It first converts the element to lowercase, for uniformity. Then it builds a feature vector whose first component is the length of the text element, in our case the number of characters of the sentence. The length feature is necessary: it prevents feature-empty sentences from being absorbed into a neighboring match for free. \pr{CountFeature} counts the number of occurrences of a feature in an element.³⁴³⁴A standard function; we will not build it. Each of these counts is added to the list \(\var{v}\).³⁵³⁵If \(v\) is a list, then \(v+\qb{z}\) denotes the list obtained by appending the single element \(z\) to \(v\).

\begin{algorithm}
\caption{Feature vector of one element.}
\begin{algorithmic}[1]
\State \textbf{Input:} an element $\var{element}$.
\State \textbf{Output:} the feature vector of $\var{element}$.
\Procedure{Text.ElementFeatures}{$\var{element}$}
    \State $\var{element} \gets \pr{Lowercase}(\var{element})$
    \State $\var{v} \gets [\pr{Length}(\var{element})]$
    \For{$1 \leq j \leq p$}
        \State $\var{v} \gets \var{v} + \qb{\pr{CountFeature}(\var{element}, \var{features}_j)}$
    \EndFor
    \Return $\var{v}$
\EndProcedure
\end{algorithmic}
\end{algorithm}

The procedure \pr{Text.ComputeFeatureMatrix} applies \pr{Text.ElementFeatures} to every element in the list of elements given to the class at initialization. Thus row \(i\) of \(F\) is the feature vector of \(\var{elements}_i\), see Alg. 2.5.3.

\begin{algorithm}
\caption{Compute the feature matrix.}
\begin{algorithmic}[1]
\State \textbf{Input:} none.
\State \textbf{Output:} the feature matrix $F$.
\Procedure{Text.ComputeFeatureMatrix}{}
    \State $F \gets \text{matrix with } |\var{elements}| \text{ rows and } |\var{features}|+1 \text{ columns}$
    \For{$1 \leq i \leq |\var{elements}|$}
        \State $F_{i} \gets \pr{ElementFeatures}(\var{elements}_i)$ \Comment{Set row $i$ of $F$.}
    \EndFor
    \Return $F$
\EndProcedure
\end{algorithmic}
\end{algorithm}

The procedure \pr{Text.ChunkFeatures}³⁶³⁶We follow the usual vector-style convention: expressions such as \(\alpha v\) are understood componentwise, just as functions such as \(\exp(x)\). represents a chunk by adding the feature vectors of its elements. If the chunk is empty, it returns the zero vector of length \(|\var{features}|+1\), see Alg. 2.5.4.

\begin{algorithm}
\caption{Feature vector of a chunk.}
\begin{algorithmic}[1]
\State \textbf{Input:} indices $a$ and $b$; the chunk is empty when $b



The dynamic-programming class stores the value functions \(J^*\)
and the optimal controls \(u^*\). Its methods are the DP objects from the model:
the transition \(T\), the feasible control set \(U\), the running cost \(g\),
the terminal cost, and the procedure for solving the DPE. The class interface is
in Alg. 2.5.5.


\begin{algorithm}
\caption{Dynamic-programming object for text matching.}
\begin{algorithmic}
\State \textbf{Input:} left text $L$, right text $R$.
\State \textbf{Output:} a dynamic-programming object.
\State \textbf{class } $\cl{TextDP}(L,R)$
\State $\quad$ \textbf{instance variables:}
\State $\quad\quad J^* \gets \text{empty map}$ \Comment{Optimal value function}
\State $\quad\quad u^* \gets \text{empty map}$ \Comment{Optimal controls}
\State $\quad\quad \var{seen\_states} \gets \varnothing$ \Comment{States for which $J^*$ is known}
\State $\quad$ \textbf{methods:}
\State $\quad\quad \pr{T}(x,u)$ \Comment{Next state after applying control $u$ in state $x$.}
\State $\quad\quad \pr{U}(x)$ \Comment{Feasible controls in state $x$.}
\State $\quad\quad \pr{g}(x,u)$ \Comment{Cost of applying control $u$ in state $x$.}
\State $\quad\quad \pr{g\_terminal}(x)$ \Comment{Terminal cost.}
\State $\quad\quad \pr{Solve}(x)$ \Comment{Solve the DPE from state $x$.}
\State $\quad\quad \pr{OptimalPath}()$ \Comment{Recover the matching by following $u^*$.}
\end{algorithmic}
\end{algorithm}



The transition \(\pr{TextDP.T}\) adds the control \(u=(i,j)\) to the current state
\(x=(\ell,r)\). The next state is therefore \((\ell+i,r+j)\), see
Alg. 2.5.6.


\begin{algorithm}
\caption{State transition for text matching.}
\begin{algorithmic}[1]
\State \textbf{Input:} state $x=(\ell,r)$ and control $u=(i,j)$.
\State \textbf{Output:} the next state.
\Procedure{TextDP.T}{$x,u$}
    \State $(\ell,r) \gets x$
    \State $(i,j) \gets u$
    \Return $(\ell+i,r+j)$
\EndProcedure
\end{algorithmic}
\end{algorithm}



The feasible control set \(U(x)\) contains matches in which at least one side
contributes exactly one element. The bounds prevent overruns beyond the two
texts, see Alg. 2.5.7.


\begin{algorithm}
\caption{Feasible controls for text matching.}
\begin{algorithmic}[1]
\State \textbf{Input:} state $x=(\ell,r)$.
\State \textbf{Output:} the feasible control set $U(x)$.
\Procedure{TextDP.U}{$x$}
    \State $(\ell,r) \gets x$
    \State $U_L \gets \varnothing$
    \State $U_R \gets \varnothing$
    \If{$\ell \leq |L|$}
        \State $U_L \gets \set{(1,j): 0 \leq j \leq \min\{\var{MAX\_MATCH},|R|+1-r\}}$
    \EndIf
    \If{$r \leq |R|$}
        \State $U_R \gets \set{(i,1): 0 \leq i \leq \min\{\var{MAX\_MATCH},|L|+1-\ell\}}$
    \EndIf
    \Return $U_L \cup U_R$
\EndProcedure
\end{algorithmic}
\end{algorithm}



The running cost \(g(x,u)\), Alg. 2.5.8, quantifies the cost of
feature vector differences between the left chunk and the right chunk. This
is only meaningful when the left and right chunk feature vectors
have the same length, and coordinate \(j\) counts the same kind of thing on
either side.


\begin{algorithm}
\caption{Running cost for text matching.}
\begin{algorithmic}[1]
\State \textbf{Input:} state $x=(\ell,r)$ and control $u$.
\State \textbf{Output:} the running cost $g(x,u)$.
\Procedure{TextDP.g}{$x,u$}
    \State $(\ell,r) \gets x$
    \State $(\ell',r') \gets \pr{T}(x,u)$
    \State $v_L \gets L.\pr{ChunkFeatures}(\ell,\ell'-1)$
    \State $v_R \gets R.\pr{ChunkFeatures}(r,r'-1)$
    \State $c \gets 0$
    \For{$1 \leq j \leq |v_L|$}
        \State $c \gets c + \var{weights}_j |v_L(j)-v_R(j)|$
    \EndFor
    \Return $c$
\EndProcedure
\end{algorithmic}
\end{algorithm}



The terminal cost is zero once both texts have been consumed. Any unmatched
remainder has already been charged by the preceding running costs, see
Alg. 2.5.9.


\begin{algorithm}
\caption{Terminal cost for text matching.}
\begin{algorithmic}[1]
\State \textbf{Input:} terminal state $x=(|L|+1,|R|+1)$.
\State \textbf{Output:} the terminal cost.
\Procedure{TextDP.g\_terminal}{$x$}
    \Return $0$
\EndProcedure
\end{algorithmic}
\end{algorithm}



The function \pr{TextDP.Solve}, see Alg. 2.5.10, solves the DPE by
recursion, and caches the result as \pr{ShortestPath} does,
Alg. 2.3.5: the same state \((\ell,r)\) is reached by several
sequences of controls. For this purpose the procedure keeps the set
\(\var{seen\_states}\) and the map \(J^*\). If a state has already been solved,
the stored value \(J^*(x)\) is returned instead of recomputed. Otherwise the
procedure minimizes \(g(x,u)+J^*(T(x,u))\) over feasible controls, stores both
\(J^*(x)\) and \(u^*(x)\), and marks \(x\) as seen. Here the cycle question does
not arise: every control advances \(\ell\) or \(r\), so a state is never
revisited.


\begin{algorithm}
\caption{Solve the dynamic programming equation.}
\begin{algorithmic}[1]
\State \textbf{Input:} state $x=(\ell,r)$.
\State \textbf{Output:} the optimal value $J^*(x)$.
\Procedure{TextDP.Solve}{$x$}
    \If{$x \in \var{seen\_states}$}
        \Return $J^*(x)$
    \EndIf
    \State $(\ell,r) \gets x$
    \If{$\ell=|L|+1$ and $r=|R|+1$}
        \State $J^*(x) \gets \pr{g\_terminal}(x)$
        \State $\var{seen\_states}.\pr{Add}(x)$
        \Return $J^*(x)$
    \EndIf
    \State $\var{best\_cost} \gets \infty$
    \State $\var{best\_control} \gets \cn{None}$
    \For{$u \in \pr{U}(x)$}
        \State $c \gets \pr{g}(x,u) + \pr{Solve}(\pr{T}(x,u))$
        \If{$c < \var{best\_cost}$}
            \State $\var{best\_cost} \gets c$
            \State $\var{best\_control} \gets u$
        \EndIf
    \EndFor
    \State $J^*(x) \gets \var{best\_cost}$
    \State $u^*(x) \gets \var{best\_control}$
    \State $\var{seen\_states}.\pr{Add}(x)$
    \Return $J^*(x)$
\EndProcedure
\end{algorithmic}
\end{algorithm}



Once the DP is solved, we use the stored controls \(u^*(x)\) to construct the
optimal matching of chunks. \(\pr{TextDP.OptimalPath}()\), see
Alg. 2.5.11, recovers this list.


\begin{algorithm}
\caption{Recover the optimal path.}
\begin{algorithmic}[1]
\State \textbf{Input:} none.
\State \textbf{Output:} the optimal list of matched chunks.
\Procedure{TextDP.OptimalPath}{}
    \State $\var{path} \gets []$
    \State $(\ell,r) \gets (1,1)$
    \While{$(\ell,r) \neq (|L|+1,|R|+1)$}
        \State $(\ell',r') \gets \pr{T}((\ell,r),u^{*}(\ell,r))$
        \State $\var{path} \gets \var{path} + \qb{((\ell,\ell'-1),(r,r'-1))}$
        \State $(\ell,r) \gets (\ell',r')$
    \EndWhile
    \Return $\var{path}$
\EndProcedure
\end{algorithmic}
\end{algorithm}

In this section we apply the above DP to make a matching for the fairy tale of Hansel and Grethel³⁷³⁷Grimm Stories, Hansel and Grethel.. We take French as source, and English as target. If you make the effort to compare the stories in the two languages on that site, you’ll quickly see that making matches is a real challenge, as the English translation does not follow the French one sentence by sentence.³⁸³⁸Both are translations of the German original, made independently of each other. Getting a perfect match is simply impossible, but with the DP we can try to get the least distracting result.

With the model above, we only have to specify the feature lists and the weights to make an optimal matching, see Alg. 2.6.1. The first of the 7 features is the length of the element \(e\), so \(f_1(e) = |e|\). The other six count how often a term occurs in \(e\).³⁹³⁹The terms are lowercase, because each sentence is lowercased before the counts are computed. For example, with the English feature list in Alg. 2.6.1, the sentence When they had gone a little way Hansel stood still and looked back towards the house, and this he did again and again, till his father said to him, “Hansel, what are you looking at? take care not to forget your legs.” has feature vector \[ (217,4,0,0,2,1,0), \] where the first entry is the number of characters of the lowercased sentence.

The content-word features receive a larger weight than the punctuation features, because we guess that names and salient objects are more important story markers than punctuation.⁴⁰⁴⁰We picked the hyperparameter 10 somewhat arbitrarily. As the above feature vector shows, character counts are much larger than term counts. By setting a weight of \(0.05\) we ensure that the length feature gets a small total weight. Like this, length differences still discourage empty or wildly unbalanced matches, but they do not dominate the other features.

\begin{algorithm}
\caption{Term lists for the Hansel and Grethel example.}
\begin{algorithmic}
\State $\var{MAX\_MATCH} \gets 4$
\State $\var{weights} \gets [0.05,1,1,10,10,10,10]$
\State $\var{french\_terms} \gets [",", "!", \text{gretel}, \text{hansel}, \text{père}, \text{canard}]$
\State $\var{english\_terms} \gets [",", "!", \text{grethel}, \text{hansel}, \text{father}, \text{duck}]$
\end{algorithmic}
\end{algorithm}

To run the matcher on the French source and the English target, the full procedure is now short. Load the texts, split them into elements,⁴¹⁴¹With the python package spacy. build the two \(\cl{Text}\) objects, solve the DPE, and recover the optimal path, see Alg. 2.6.2. The result is a list of matched chunks.⁴²⁴²With the LaTeX paracol package we make the two-column document.

\begin{algorithm}
\caption{Run the matcher on the French and English texts.}
\begin{algorithmic}[1]
\State \textbf{Input:} French source text and English target text.
\State \textbf{Output:} a list of matched chunks.
\State $\var{french\_elements} \gets \pr{SplitIntoElements}(\var{french\_source})$
\State $\var{english\_elements} \gets \pr{SplitIntoElements}(\var{english\_target})$
\State $L \gets \cl{Text}(\var{french\_elements}, \var{french\_terms})$
\State $R \gets \cl{Text}(\var{english\_elements}, \var{english\_terms})$
\State $\var{dp} \gets \cl{TextDP}(L,R)$
\State $\var{dp}.\pr{Solve}((1,1))$
\State $\var{path} \gets \var{dp}.\pr{OptimalPath}()$
\Return $\var{path}$
\end{algorithmic}
\end{algorithm}

The final French-English parallel translation, and the Dutch-English version, are in Chapter C. Whether the result is acceptable is up to the user.⁴³⁴³For me it sufficed when I needed it. If it is not, the sentence splitter can be improved: the French splitter is not very good, as the result shows. We can also add more features, or enlarge the control set so that several left elements can be matched to several right elements. This would capture the merge-and-resplit that the current one-to-many controls cannot represent.