Text Alignment

Smith Waterman

Smith-Waterman is an algorithm to identify similaries between sequences. The algorithm is explained in detail at https://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorithm and finds a local optimal alignment between 2 sequences of letters.

This package implements the algorithm for sequences of letters as well as sequences of words and is usefull for text analytics researchers.

  • The package uses similar code as the textreuse::local_align function and also allows to align character sequences next to aligning word sequences

Example usage

The package was set up in order to easily

  • Find names in documents even if they are not correctly spelled
  • Match 2 texts
  • Find relevant sequences of texts in other texts

We show some examples of these use cases below.

library(text.alignment)

Example matching 2 names

a <- "Gaspard   Tournelly cardeur à laine"
b <- "Gaspard   Bourelly cordonnier"
smith_waterman(a, b)
Swith Waterman local alignment score: 35
----------
Document a
----------
Gaspard T#ournelly ca#rd
----------
Document b
----------
Gaspard #Bour#elly c#ord
a <- "Gaspard   T.  cardeur à laine"
b <- "Gaspard   Tournelly cardeur à laine"
smith_waterman(a, b, type = "characters")
Swith Waterman local alignment score: 39
----------
Document a
----------
Gaspard T.# ########cardeur à laine
----------
Document b
----------
Gaspard T#o#urnelly cardeur à laine

Example matching 2 translations

a <- system.file(package = "text.alignment", "extdata", "example1.txt")
a <- readLines(a)
a <- paste(a, collapse = "\n")
b <- system.file(package = "text.alignment", "extdata", "example2.txt")
b <- readLines(b)
b <- paste(b, collapse = "\n")
cat(a, sep = "\n")
Actum den 15e april 1709
Jan Mortier filius Jan oudt 43 jaeren ghebooren van Hontschote bleecker
op de groote St Gillisbleeckerie op de Langhereije claeght dat
dese nacht op sijn bleeckerie sijng hestolen 45 hemden van mans ende
vrauhemden, daer onder twee kinderhemden toebehoorende aen
Jaspar Tant, ondewende dat het moet ghebeurt wesen
tusschen 12 ende 2 heuren van voorleden naght,
sijnde in huijseken ter suijtsijde ghenaempt het Lant van
Beloften,
alwaer ses ruijtters gelogiert, ende van achter
de smisse staet daer daergelix soldaeten commen, ende 
alwaer in tdijkje light, waermede hij oirdeelt  
dat eenighe ruijters sijn overgecommen, alsoo
eker vrauw woonende in taen De Vos  voorseijde  huijseken
heeft hooren snachts tusschen  12 ende 1 heuren open gaende poorte 
van diere  staende bij de huijsse uut commende in de 
Baillestraete, ende dat seker ruijtter woonende in  het
Ghistelhof sere frequenteert met de voorseijde ruijtters
daer oppe die vrauwe  eenighe  suspirie hadde, woonende
in t' voorseijde huijseken sieur  De Vos geweest roedraerigh
van St Gillis kercke aldaer uut de kercke geseijt
op welcken tijdt ghewacht heeft opde bleeckerie
s'claehgers ende op het bassen van d'honden is den claegher opghestaen ende ghesien de voorseijde hemde
ghestolen, sonder nochtans iemant ghesien te hebben
cat(b, sep = "\n")
Actum den 15e april 1709
Jan Mortier fs Jan oudt 43 jaeren gebooren van Hontscote bleecker
op de groote St Gilisbleeckerie op de Langerije claeght dat
dese nacht op sijn bleeckerie sijn ghestolen 45 hemden van mans vrauhemden, daeronder twee kinderhemden toebehoorende aen
Jaspar Tant, oordelende dat het moet ghebeurt wesen
tusschen 12 ende 2 heuren vande voorleden nacht,
sijnde in huijseken ter suijtsijde ghenaempt het Lant van
Beloften, alwaer ses ruijtters ghelogiert ende van achter
aen smisse staet daer daegelix soldaeten commen, ende 
alwaer ien deijkje light, waermede hij oirdeelt
dat eenige ruijtters sijn overgecommen,  alsoo
seker vrauwe woonende in een camer vande voorseijde huijseken
heeft hooren snachts tusscen 12 ende 1 heuren open gaen een poortken
van diere staende bij de smisse uitcommende in de
Bailliestraete, ende dat seker ruijtter woonende  in het
Gistelhof sere frequenteert met de vooseijde ruijtters
daeroppe die vrauwe eenige suspirie hadde, woonende
in t'voorseijde huijseken jonker De Vos gheweest roedraeger
van St Gillis kercke aldaer uut de kercke gheseijt,
op welcken tijdt ghewacht heeft op de bleeckerie
s' claeghers huijsvrauwe ende op het bassen van d'honden
is en claegher opghestaen ende ghesien de voorseijde hemde
gestolen, sonder nochtans iemant geseien thebben
smith_waterman(a, b, type = "words")
Swith Waterman local alignment score: 260
----------
Document a
----------
Actum den 15e april 1709 Jan Mortier filius ## Jan oudt 43 jaeren
ghebooren ######## van Hontschote ######### bleecker op de groote St
Gillisbleeckerie ############### op de Langhereije ######### claeght
dat dese nacht op sijn bleeckerie sijng #### hestolen ######### 45
hemden van mans ende vrauhemden daer ######### onder twee kinderhemden
toebehoorende aen Jaspar Tant ondewende ########## dat het moet
ghebeurt wesen tusschen 12 ende 2 heuren van ##### voorleden naght
##### sijnde in huijseken ter suijtsijde ghenaempt het Lant van
Beloften alwaer ses ruijtters gelogiert ########## ende van achter de
### smisse staet daer daergelix ######## soldaeten commen ende alwaer
in ### tdijkje ####### light waermede hij oirdeelt dat eenighe ######
ruijters ######### sijn overgecommen alsoo eker ##### vrauw ######
woonende in taen ### De ##### Vos ##### voorseijde huijseken heeft
hooren snachts tusschen ####### 12 ende 1 heuren open gaende ####
poorte ### ######## van diere staende bij de huijsse ###### uut
########### commende in de Baillestraete ############## ende dat seker
ruijtter woonende in het Ghistelhof ######### sere frequenteert met de
voorseijde ######### ruijtters daer ######## oppe die vrauwe eenighe
###### suspirie hadde woonende in t voorseijde huijseken sieur ######
De Vos geweest ######## roedraerigh ########## van St Gillis kercke
aldaer uut de kercke geseijt ######## op welcken tijdt ghewacht heeft
opde ## ## bleeckerie s claehgers ######### ########### ende op het
bassen van d honden is den ## claegher opghestaen ende ghesien de
voorseijde hemde ghestolen ######## sonder nochtans iemant
----------
Document b
----------
Actum den 15e april 1709 Jan Mortier ###### fs Jan oudt 43 jaeren
######### gebooren van ########## Hontscote bleecker op de groote St
################ Gilisbleeckerie op de ########### Langerije claeght
dat dese nacht op sijn bleeckerie ##### sijn ######## ghestolen 45
hemden van mans #### vrauhemden #### daeronder ##### twee kinderhemden
toebehoorende aen Jaspar Tant ######### oordelende dat het moet
ghebeurt wesen tusschen 12 ende 2 heuren ### vande voorleden #####
nacht sijnde in huijseken ter suijtsijde ghenaempt het Lant van
Beloften alwaer ses ruijtters ######### ghelogiert ende van achter ##
aen smisse staet daer ######### daegelix soldaeten commen ende alwaer
## ien ####### deijkje light waermede hij oirdeelt dat ####### eenige
######## ruijtters sijn overgecommen alsoo #### seker ##### vrauwe
woonende in #### een ## camer ### vande voorseijde huijseken heeft
hooren snachts ######## tusscen 12 ende 1 heuren open ###### gaen
###### een poortken van diere staende bij de ####### smisse ###
uitcommende ######## in de ############# Bailliestraete ende dat seker
ruijtter woonende in het ########## Gistelhof sere frequenteert met de
########## vooseijde ruijtters #### daeroppe #### die vrauwe #######
eenige suspirie hadde woonende in t voorseijde huijseken ##### jonker
De Vos ####### gheweest ########### roedraeger van St Gillis kercke
aldaer uut de kercke ####### gheseijt op welcken tijdt ghewacht heeft
#### op de bleeckerie s ######### claeghers huijsvrauwe ende op het
bassen van d honden is ### en claegher opghestaen ende ghesien de
voorseijde hemde ######### gestolen sonder nochtans iemant

Find relevant sequences of texts in other texts

x <- smith_waterman("Lange rei", b)
x$b$tokens[x$b$alignment$from:x$b$alignment$to]
[1] "L" "a" "n" "g" "e" "r" "i"
overview <- as.data.frame(x)
overview$b_from
[1] 130
overview$b_to
[1] 136
substr(overview$b, overview$b_from, overview$b_to)
[1] "Langeri"

Get alignment overview as a data.frame

x <- smith_waterman(a, b)
x <- as.data.frame(x, alignment_id = "matching-a-to-b")
str(x)
'data.frame':   1 obs. of  23 variables:
 $ alignment_id: chr "matching-a-to-b"
 $ a           : chr "Actum den 15e april 1709\nJan Mortier filius Jan oudt 43 jaeren ghebooren van Hontschote bleecker\nop de groote"| __truncated__
 $ b           : chr "Actum den 15e april 1709\nJan Mortier fs Jan oudt 43 jaeren gebooren van Hontscote bleecker\nop de groote St Gi"| __truncated__
 $ sw          : int 2386
 $ similarity  : num 0.911
 $ matches     : int 1246
 $ mismatches  : int 17
 $ a_n         : int 1315
 $ a_aligned   : chr "Actum den 15e april 1709\nJan Mortier filius Jan oudt 43 jaeren ghebooren van Hontschote bleecker\nop de groote"| __truncated__
 $ a_similarity: num 0.907
 $ a_gaps      : int 47
 $ a_from      : num 1
 $ a_to        : num 1315
 $ a_fromto    :List of 1
  ..$ : chr  "A" "c" "t" "u" ...
  ..- attr(*, "class")= chr "AsIs"
 $ a_misaligned:List of 1
  ..$ :List of 5
  .. ..$ before_alignment: chr 
  .. ..$ wrong_alignment : chr  "i" "l" "i" "u" ...
  .. ..$ after_alignment : chr 
  .. ..$ combined        : chr  "i" "l" "i" "u" ...
  .. ..$ partial         : logi TRUE
  ..- attr(*, "class")= chr "AsIs"
 $ b_n         : int 1310
 $ b_aligned   : chr "Actum den 15e april 1709\nJan Mortier f####s Jan oudt 43 jaeren g#ebooren van Hontsc#ote bleecker\nop de groote"| __truncated__
 $ b_similarity: num 0.911
 $ b_gaps      : int 52
 $ b_from      : num 1
 $ b_to        : num 1310
 $ b_fromto    :List of 1
  ..$ : chr  "A" "c" "t" "u" ...
  ..- attr(*, "class")= chr "AsIs"
 $ b_misaligned:List of 1
  ..$ :List of 5
  .. ..$ before_alignment: chr 
  .. ..$ wrong_alignment : chr  "g" "o" "r" "l" ...
  .. ..$ after_alignment : chr 
  .. ..$ combined        : chr  "g" "o" "r" "l" ...
  .. ..$ partial         : logi TRUE
  ..- attr(*, "class")= chr "AsIs"