# Text Alignment

#### Jan Wijffels

#### 2020-09-08

## 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"