Module: TextAlignment

Defined in:
lib/text_alignment/constants.rb,
lib/text_alignment/lcs_cdiff.rb,
lib/text_alignment/char_mapping.rb,
lib/text_alignment/anchor_finder.rb,
lib/text_alignment/glcs_required.rb,
lib/text_alignment/find_divisions.rb,
lib/text_alignment/glcs_alignment.rb,
lib/text_alignment/lcs_comparison.rb,
lib/text_alignment/text_alignment.rb,
lib/text_alignment/approximate_fit.rb,
lib/text_alignment/cultivation_map.rb,
lib/text_alignment/mixed_alignment.rb,
lib/text_alignment/glcs_alignment_fast.rb

Defined Under Namespace

Classes: AnchorFinder, CharMapping, CultivationMap, GLCSAlignment, GLCSTextAlignment, LCSAlignment, LCSComparison, LCSMin, MixedAlignment, TextAlignment

Constant Summary collapse

SIZE_NGRAM = 
8
SIZE_WINDOW = 
10
BUFFER_RATE = 
0.1
BUFFER_MIN = 
20
TEXT_SIMILARITY_THRESHOLD = 
0.9
NIL_CHARACTER = 
'_'
CHAR_MAPPING = 
[
  ["©", "(c)"],      #U+00A9 (Copyright Sign)

  ["α", "alpha"],    #U+03B1 (greek small letter alpha)
  ["β", "beta"],   #U+03B2 (greek small letter beta)
  ["γ", "gamma"],    #U+03B3 (greek small letter gamma)
  ["δ", "delta"],    #U+03B4 (greek small letter delta)
  ["ε", "epsilon"],  #U+03B5 (greek small letter epsilon)
  ["ζ", "zeta"],   #U+03B6 (greek small letter zeta)
  ["η", "eta"],      #U+03B7 (greek small letter eta)
  ["θ", "theta"],    #U+03B7 (greek small letter eta)
  ["ι", "iota"],   #U+03B7 (greek small letter eta)
  ["κ", "kappa"],    #U+03BA (greek small letter kappa)
  ["λ", "lambda"], #U+03BB (greek small letter lambda)
  ["λ", "lamda"],    #U+03BB (greek small letter lambda)
  ["μ", "mu"],     #U+03BC (greek small letter mu)
  ["ν", "nu"],     #U+03BD (greek small letter nu)
  ["ξ", "xi"],     #U+03BE (greek small letter xi)
  ["ο", "omicron"],  #U+03BF (greek small letter omicron)
  ["π", "pi"],     #U+03C0 (greek small letter pi)
  ["ρ", "rho"],      #U+03C1 (greek small letter rho)
  ["σ", "sigma"],    #U+03C3 (greek small letter sigma)
  ["τ", "tau"],      #U+03C4 (greek small letter tau)
  ["υ", "upsilon"],  #U+03C5 (greek small letter upsilon)
  ["φ", "phi"],      #U+03C6 (greek small letter phi)
  ["χ", "chi"],      #U+03C7 (greek small letter chi)
  ["ψ", "psi"],      #U+03C8 (greek small letter psi)
  ["ω", "omega"],    #U+03C9 (greek small letter omega)

  ["Α", "Alpha"],    #U+0391 (greek capital letter alpha)
  ["Β", "Beta"],   #U+0392 (greek capital letter beta)
  ["Γ", "Gamma"],    #U+0393 (greek capital letter gamma)
  ["Δ", "Delta"],    #U+0394 (greek capital letter delta)
  ["Ε", "Epsilon"],  #U+0395 (greek capital letter epsilon)
  ["Ζ", "Zeta"],   #U+0396 (greek capital letter zeta)
  ["Η", "Eta"],      #U+0397 (greek capital letter eta)
  ["Θ", "Theta"],    #U+0398 (greek capital letter theta)
  ["Ι", "Iota"],   #U+0399 (greek capital letter iota)
  ["Κ", "Kappa"],    #U+039A (greek capital letter kappa)
  ["Λ", "Lambda"], #U+039B (greek capital letter lambda)
  ["Λ", "Lamda"],    #U+039B (greek capital letter lambda)
  ["Μ", "Mu"],     #U+039C (greek capital letter mu)
  ["Ν", "Nu"],     #U+039D (greek capital letter nu)
  ["Ξ", "Xi"],     #U+039E (greek capital letter xi)
  ["Ο", "Omicron"],  #U+039F (greek capital letter omicron)
  ["Π", "Pi"],     #U+03A0 (greek capital letter pi)
  ["Ρ", "Rho"],      #U+03A1 (greek capital letter rho)
  ["Σ", "Sigma"],    #U+03A3 (greek capital letter sigma)
  ["Τ", "Tau"],      #U+03A4 (greek capital letter tau)
  ["Υ", "Upsilon"],  #U+03A5 (greek capital letter upsilon)
  ["Φ", "Phi"],      #U+03A6 (greek capital letter phi)
  ["Χ", "Chi"],      #U+03A7 (greek capital letter chi)
  ["Ψ", "Psi"],      #U+03A8 (greek capital letter Psi)
  ["Ω", "Omega"],    #U+03A9 (greek capital letter omega)

  ["ϕ", "phi"],      #U+03D5 (greek phi symbol)

  ["×", "x"],        #U+00D7 (multiplication sign)
  ["•", "*"],        #U+2022 (bullet)
  [" ", " "],        #U+2009 (thin space)
  [" ", " "],        #U+200A (hair space)
  [" ", " "],        #U+202F (narrow no-break space)
  [" ", " "],        #U+00A0 (Non-Breaking space)
  ["　", " "],        #U+3000 (ideographic space)
  ["‐", "-"],        #U+2010 (Hyphen)
  ["‑", "-"],        #U+2011 (Non-Breaking Hyphen)
  ["−", "-"],        #U+2212 (minus sign)
  ["–", "-"],        #U+2013 (en dash)
  ["′", "'"],        #U+2032 (prime)
  ["‘", "'"],        #U+2018 (left single quotation mark)
  ["’", "'"],        #U+2019 (right single quotation mark)
  ["“", '"'],        #U+201C (left double quotation mark)
  ["”", '"'],        #U+201D (right double quotation mark)
  ['"', "''"]
]
SIMILARITY_THRESHOLD =

to work on the hash representation of denotations to assume that there is no bag representation to this method

0.7
MIN_LENGTH_FOR_APPROXIMATION =

approximate the location of str1 in str2

50

Class Method Summary collapse

Class Method Details

._find_divisions(_source, _targets) ⇒ Object 



35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
 
# File 'lib/text_alignment/find_divisions.rb', line 35

def _find_divisions(_source, _targets)
  indice = []
  history = []
  cache = {}
  source = _source.dup
  targets = _targets.dup
  until source.strip.empty? || targets.empty?
    mode, cmp = nil, nil
    candidates = []
    targets.each_with_index do |target, i|
      if source.size < target[:text].size
        mode = :t_in_s
        str1 = source
        str2 = target[:text]
      else
        mode = :s_in_t
        str1 = target[:text]
        str2 = source
      end

      len1 = str1.length
      len2 = str2.length

      offset_begin, offset_end = if (len2 - len1) > len1 * (1 - TextAlignment::SIMILARITY_THRESHOLD)
        approximate_fit(str1, str2)
      else
        # the whole source
        [0, -1]
      end

      unless offset_begin.nil?
        key = str1 + ' _:_ ' + str2[offset_begin .. offset_end]
        cmp = if cache.has_key? key
          cache[key]
        else
          cmp = TextAlignment::LCSComparison.new(str1, str2[offset_begin .. offset_end])
        end
        cache[key] = cmp

        if (cmp.similarity > TextAlignment::SIMILARITY_THRESHOLD) && ((len1 - (cmp.str1_match_final - cmp.str1_match_initial + 1)) < len1 * (1 - TextAlignment::SIMILARITY_THRESHOLD))
          candidates << {idx:i, offset:offset_begin, mode:mode, cmp:cmp}
        end
      end
    end

    # return remaining source and targets if m.nil?
    break if candidates.empty?

    choice = candidates.max{|a, b| a[:cmp].similarity <=> a[:cmp].similarity}
    m = choice[:idx]
    mode = choice[:mode]

    index = if mode == :t_in_s
      {divid:targets[m][:divid], region:[0, source.size]}
    else # :s_in_t
      cmp = choice[:cmp]
      offset = choice[:offset]
      {divid:targets[m][:divid], region:[cmp.str2_match_initial + offset, cmp.str2_match_final + offset + 1]}
    end

    source = source[0 ... index[:region][0]] + source[index[:region][1] .. -1]
    history << index[:region].dup

    before_begin = index[:region][0]
    before_end = index[:region][1]

    rhistory = history.reverse
    rhistory.shift
    rhistory.each do |h|
      gap = h[1] - h[0]
      index[:region][0] += gap if index[:region][0] >= h[0]
      index[:region][1] += gap if index[:region][1] >  h[0]
    end

    indice << index

    targets.delete_at(m)
  end

  unless source.strip.empty? && targets.empty?
    index = {divid:nil}
    index[:remaining_source] = source unless source.strip.empty?
    index[:remaining_targets] = targets.collect{|s| s[:divid]} unless targets.empty?
    indice << index
  end

  indice
end

._find_divisions_old(source, targets) ⇒ Object 



124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
 
# File 'lib/text_alignment/find_divisions.rb', line 124

def _find_divisions_old(source, targets)
  mode, m, c, offset_begin = nil, nil, nil, nil

  targets.each_with_index do |target, i|
    if source.size < target[:text].size
      mode = :t_in_s
      str1 = source
      str2 = target[:text]
    else
      mode = :s_in_t
      str1 = target[:text]
      str2 = source
    end

    len1 = str1.length
    len2 = str2.length

    offset_begin, offset_end = 0, -1
    offset_begin, offset_end = approximate_fit(str1, str2) if (len2 - len1) > len1 * (1 - TextAlignment::SIMILARITY_THRESHOLD)

    unless offset_begin.nil?
      c = TextAlignment::LCSComparison.new(str1, str2[offset_begin .. offset_end])
      if (c.similarity > TextAlignment::SIMILARITY_THRESHOLD) && ((len1 - (c.str1_match_final - c.str1_match_initial + 1)) < len1 * (1 - TextAlignment::SIMILARITY_THRESHOLD))
        m = i
        break
      end
    end
  end

  # return remaining source and targets if m.nil?
  return [[-1, [source, targets.collect{|s| s[:divid]}]]] if m.nil?

  index = if mode == :t_in_s
    [targets[m][:divid], [0, source.size]]
  else # :s_in_t
    [targets[m][:divid], [c.str2_match_initial + offset_begin, c.str2_match_final + offset_begin + 1]]
  end

  next_source = source[0 ... index[1][0]] + source[index[1][1] .. -1]
  targets.delete_at(m)

  if next_source.strip.empty? || targets.empty?
    return [index]
  else
    more_index = _find_divisions(next_source, targets)
    gap = index[1][1] - index[1][0]
    more_index.each do |i|
      if (i[0] > -1)
        i[1][0] += gap if i[1][0] >= index[1][0]
        i[1][1] += gap if i[1][1] >  index[1][0]
      end
    end
    return [index] + more_index
  end
end

.approximate_fit(str1, str2) ⇒ Object

If finds an approximate region of str2 that contains str1

Raises:

  • (ArgumentError) 


13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
# File 'lib/text_alignment/approximate_fit.rb', line 13

def approximate_fit(str1, str2)
  raise ArgumentError, 'nil string' if str1.nil? || str2.nil?
  return 0, str2.length if str2.length < TextAlignment::MIN_LENGTH_FOR_APPROXIMATION

  ngram1 = (0 .. str1.length - TextAlignment::SIZE_NGRAM).collect{|i| str1[i, TextAlignment::SIZE_NGRAM]}
  ngram2 = (0 .. str2.length - TextAlignment::SIZE_NGRAM).collect{|i| str2[i, TextAlignment::SIZE_NGRAM]}
  ngram_shared = ngram1 & ngram2

  # If there is no shared n-gram found, it may mean there is no serious overlap between the two strings
  return nil, nil if ngram_shared.empty?

  signature_ngrams = ngram_shared.select{|g| ngram2.count(g) == 1}
  return nil, nil if signature_ngrams.empty? #raise "no signature ngram"

  cache = {}
  fit_begin, fit_end = nil, nil
  signature_ngrams.each do |signature_ngram|
    loc_signature_ngram_in_str1 = str1.index(signature_ngram)
    loc_signature_ngram_in_str2 = str2.index(signature_ngram)

    # approximate the beginning of the fit
    fit_begin = loc_signature_ngram_in_str2 - loc_signature_ngram_in_str1 - (loc_signature_ngram_in_str1 * TextAlignment::BUFFER_RATE).to_i
    fit_begin = 0 if fit_begin < 0

    # approximate the end of the fit
    offset_end = str1.length - loc_signature_ngram_in_str1
    fit_end = loc_signature_ngram_in_str2 + offset_end + (offset_end * TextAlignment::BUFFER_RATE).to_i
    fit_end = str2.length if fit_end > str2.length

    next if cache.has_key?("#{fit_begin}-#{fit_end}")
    text_similarity = text_similarity(str1, str2[fit_begin ... fit_end])
    cache["#{fit_begin}-#{fit_end}"] = text_similarity

    break if text_similarity > TextAlignment::TEXT_SIMILARITY_THRESHOLD
    fit_begin, fit_end = nil, nil
  end
  return fit_begin, fit_end if fit_begin && fit_end && fit_begin < fit_end
  return nil, nil
end

.cdiff(str1, str2) ⇒ Object

Raises:

  • (ArgumentError) 


10
11
12
13
14
 
# File 'lib/text_alignment/lcs_cdiff.rb', line 10

def cdiff(str1, str2)
  raise ArgumentError, "nil string" if str1.nil? || str2.nil?
  raise "a nil character appears in the input string" if str1.index(TextAlignment::NIL_CHARACTER) || str2.index(TextAlignment::NIL_CHARACTER)
  sdiff2cdiff(Diff::LCS.sdiff(str1, str2))
end

.find_divisions(source, targets, mappings = []) ⇒ Object

It finds, among the targets, the right divisions for the taraget text to fit in.

Raises:

  • (ArgumentError) 


15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 
# File 'lib/text_alignment/find_divisions.rb', line 15

def find_divisions(source, targets, mappings = [])
  raise ArgumentError, "nil source"           if source == nil
  raise ArgumentError, "nil or empty targets" if targets == nil || targets.empty?
  raise ArgumentError, "nil mappings"         if mappings == nil

  character_mappings = mappings.select{|m| m[0].length == 1 && m[1].length == 1}
  mappings.delete_if{|m| m[0].length == 1 && m[1].length == 1}
  characters_from = character_mappings.collect{|m| m[0]}.join
  characters_to   = character_mappings.collect{|m| m[1]}.join
  characters_to.gsub!(/-/, '\-')

  source.tr!(characters_from, characters_to)
  targets.each{|target| target[:text].tr!(characters_from, characters_to)}

  # to process smaller ones first
  targets.sort!{|s1, s2| s1[:text].size <=> s2[:text].size}

  TextAlignment._find_divisions(source, targets)
end

.glcs_required?(str1, mappings = []) ⇒ Boolean

Returns:

  • (Boolean)

Raises:

  • (ArgumentError) 


5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
# File 'lib/text_alignment/glcs_required.rb', line 5

def glcs_required?(str1, mappings = [])
  raise ArgumentError, "nil string" if str1.nil?
  raise ArgumentError, "nil mappings" if mappings.nil?

  # character mappings can be safely applied to the strings withoug changing the position of other characters
  character_mappings = mappings.select{|m| m[0].length == 1 && m[1].length == 1}
  characters_from = character_mappings.collect{|m| m[0]}.join
  characters_to   = character_mappings.collect{|m| m[1]}.join
  characters_to.gsub!(/-/, '\-')

  str1.tr!(characters_from, characters_to)

  str1 =~/([^\p{ASCII}][^\p{ASCII}])/
  $1
end

.sdiff2cdiff(sdiff) ⇒ Object

Raises:

  • (ArgumentError) 


16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
# File 'lib/text_alignment/lcs_cdiff.rb', line 16

def sdiff2cdiff (sdiff)
  raise ArgumentError, "nil sdiff" if sdiff.nil?

  cdiff_str1, cdiff_str2 = '', ''

  sdiff.each do |h|
    case h.action
    when '='
      cdiff_str1 += h.old_element
      cdiff_str2 += h.new_element
    when '!'
      cdiff_str1 += h.old_element + TextAlignment::NIL_CHARACTER
      cdiff_str2 += TextAlignment::NIL_CHARACTER + h.new_element
    when '-'
      cdiff_str1 += h.old_element
      cdiff_str2 += TextAlignment::NIL_CHARACTER
    when '+'
      cdiff_str1 += TextAlignment::NIL_CHARACTER
      cdiff_str2 += h.new_element
    end
  end

  cdiff_str1.gsub(/\n/, ' ') + "\n>>>>><<<<<\n" + cdiff_str2.gsub(/\n/, ' ')
end