Module: LangExtract::Core::SequenceMatcher

Defined in:
lib/langextract/core/token_similarity.rb

Overview

Longest-common-substring sequence matcher used for per-token character similarity scoring (equivalent to Python's SequenceMatcher.ratio()).

Defined Under Namespace

Classes: Match

Class Method Summary collapse

Class Method Details

.longest_common_substring(left_chars, right_chars, left_range, right_range) ⇒ Object 



126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
 
# File 'lib/langextract/core/token_similarity.rb', line 126

def longest_common_substring(left_chars, right_chars, left_range, right_range)
  best = Match.new(left_start: left_range.begin, right_start: right_range.begin, span_length: 0)
  previous_lengths = Array.new(right_range.size + 1, 0)

  left_range.each do |left_index|
    current_lengths = Array.new(right_range.size + 1, 0)
    right_range.each_with_index do |right_index, offset|
      next unless left_chars[left_index] == right_chars[right_index]

      length = previous_lengths[offset] + 1
      current_lengths[offset + 1] = length
      next unless length > best.span_length

      best = Match.new(
        left_start: left_index - length + 1,
        right_start: right_index - length + 1,
        span_length: length
      )
    end
    previous_lengths = current_lengths
  end

  best
end

.match_count(left_chars, right_chars) ⇒ Object 



104
105
106
 
# File 'lib/langextract/core/token_similarity.rb', line 104

def match_count(left_chars, right_chars)
  recursive_match_count(left_chars, right_chars, 0...left_chars.length, 0...right_chars.length)
end

.recursive_match_count(left_chars, right_chars, left_range, right_range) ⇒ Object 



108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
 
# File 'lib/langextract/core/token_similarity.rb', line 108

def recursive_match_count(left_chars, right_chars, left_range, right_range)
  match = longest_common_substring(left_chars, right_chars, left_range, right_range)
  return 0 unless match.span_length.positive?

  left_count = recursive_match_count(
    left_chars, right_chars,
    left_range.begin...match.left_start,
    right_range.begin...match.right_start
  )
  right_count = recursive_match_count(
    left_chars, right_chars,
    (match.left_start + match.span_length)...left_range.end,
    (match.right_start + match.span_length)...right_range.end
  )

  match.span_length + left_count + right_count
end