################################################################
# #
# stringDistance #
# #
################################################################
package NLP::stringDistance;
use List::Util qw(min max);
$utf8 = NLP::UTF8;
$util = NLP::utilities;
$romanizer = NLP::Romanizer;
%dummy_ht = ();
sub rule_string_expansion {
local($this, *ht, $s, $lang_code) = @_;
my @characters = $utf8->split_into_utf8_characters($s, "return only chars, return trailing whitespaces", *dummy_ht);
foreach $sub_len ((0 .. ($#characters-1))) {
my $sub = join("", @characters[0 .. $sub_len]);
foreach $super_len ((($sub_len + 1) .. $#characters)) {
my $super = join("", @characters[0 .. $super_len]);
# print STDERR " $sub -> $super\n" unless $ht{RULE_STRING_EXPANSION}->{$lang_code}->{$sub}->{$super};
$ht{RULE_STRING_EXPANSION}->{$lang_code}->{$sub}->{$super} = 1;
$ht{RULE_STRING_HAS_EXPANSION}->{$lang_code}->{$sub} = 1;
# print STDERR " RULE_STRING_HAS_EXPANSION $lang_code $sub\n";
}
}
}
sub load_string_distance_data {
local($this, $filename, *ht, $verbose) = @_;
$verbose = 0 unless defined($verbose);
open(IN,$filename) || die "Could not open $filename";
my $line_number = 0;
my $n_cost_rules = 0;
while (<IN>) {
$line_number++;
my $line = $_;
$line =~ s/^\xEF\xBB\xBF//;
$line =~ s/\s*$//;
next if $line =~ /^\s*(\#.*)?$/;
print STDERR "** Warning: line $line_number contains suspicious control character: $line\n" if $line =~ /[\x00-\x1F]/;
my $s1 = $util->slot_value_in_double_colon_del_list($line, "s1");
my $s2 = $util->slot_value_in_double_colon_del_list($line, "s2");
$s1 = $util->dequote_string($s1); # 'can\'t' => can't
$s2 = $util->dequote_string($s2);
my $cost = $util->slot_value_in_double_colon_del_list($line, "cost");
if (($s1 eq "") && ($s2 eq "")) {
print STDERR "Ignoring bad line $line_number in $filename, because both s1 and s2 are empty strings\n";
next;
}
unless ($cost =~ /^\d+(\.\d+)?$/) {
if ($cost eq "") {
print STDERR "Ignoring bad line $line_number in $filename, because of missing cost\n";
} else {
print STDERR "Ignoring bad line $line_number in $filename, because of ill-formed cost $cost\n";
}
next;
}
my $lang_code1_s = $util->slot_value_in_double_colon_del_list($line, "lc1");
my $lang_code2_s = $util->slot_value_in_double_colon_del_list($line, "lc2");
my @lang_codes_1 = ($lang_code1_s eq "") ? ("") : split(/,\s*/, $lang_code1_s);
my @lang_codes_2 = ($lang_code2_s eq "") ? ("") : split(/,\s*/, $lang_code2_s);
my $left_context1 = $util->slot_value_in_double_colon_del_list($line, "left1");
my $left_context2 = $util->slot_value_in_double_colon_del_list($line, "left2");
my $right_context1 = $util->slot_value_in_double_colon_del_list($line, "right1");
my $right_context2 = $util->slot_value_in_double_colon_del_list($line, "right2");
my $bad_left = $util->slot_value_in_double_colon_del_list($line, "left");
if ($bad_left) {
print STDERR "** Warning: slot '::left $bad_left' in line $line_number\n";
next;
}
my $bad_right = $util->slot_value_in_double_colon_del_list($line, "right");
if ($bad_right) {
print STDERR "** Warning: slot '::right $bad_right' in line $line_number\n";
next;
}
my $in_lang_codes1 = $util->slot_value_in_double_colon_del_list($line, "in-lc1");
my $in_lang_codes2 = $util->slot_value_in_double_colon_del_list($line, "in-lc2");
my $out_lang_codes1 = $util->slot_value_in_double_colon_del_list($line, "out-lc1");
my $out_lang_codes2 = $util->slot_value_in_double_colon_del_list($line, "out-lc2");
if ($left_context1) {
if ($left_context1 =~ /^\/.*\/$/) {
$left_context1 =~ s/^\///;
$left_context1 =~ s/\/$//;
} else {
print STDERR "Ignoring unrecognized non-regular-express ::left1 $left_context1 in $line_number of $filename\n";
$left_context1 = "";
}
}
if ($left_context2) {
if ($left_context2 =~ /^\/.*\/$/) {
$left_context2 =~ s/^\///;
$left_context2 =~ s/\/$//;
} else {
$left_context2 = "";
print STDERR "Ignoring unrecognized non-regular-express ::left2 $left_context2 in $line_number of $filename\n";
}
}
if ($right_context1) {
unless ($right_context1 =~ /^(\[[^\[\]]*\])+$/) {
$right_context1 = "";
print STDERR "Ignoring unrecognized right-context ::right1 $right_context1 in $line_number of $filename\n";
}
}
if ($right_context2) {
unless ($right_context2 =~ /^(\[[^\[\]]*\])+$/) {
$right_context2 = "";
print STDERR "Ignoring unrecognized right-context ::right2 $right_context2 in $line_number of $filename\n";
}
}
foreach $lang_code1 (@lang_codes_1) {
foreach $lang_code2 (@lang_codes_2) {
$n_cost_rules++;
my $cost_rule_id = $n_cost_rules;
$ht{COST}->{$lang_code1}->{$lang_code2}->{$s1}->{$s2}->{$cost_rule_id} = $cost;
$ht{RULE_STRING}->{$lang_code1}->{$s1} = 1;
$ht{RULE_STRING}->{$lang_code2}->{$s2} = 1;
$ht{LEFT1}->{$cost_rule_id} = $left_context1;
$ht{LEFT2}->{$cost_rule_id} = $left_context2;
$ht{RIGHT1}->{$cost_rule_id} = $right_context1;
$ht{RIGHT2}->{$cost_rule_id} = $right_context2;
$ht{INLC1}->{$cost_rule_id} = $in_lang_codes1;
$ht{INLC2}->{$cost_rule_id} = $in_lang_codes2;
$ht{OUTLC1}->{$cost_rule_id} = $out_lang_codes1;
$ht{OUTLC2}->{$cost_rule_id} = $out_lang_codes2;
unless (($s1 eq $s2)
&& ($lang_code1 eq $lang_code2)
&& ($left_context1 eq $left_context2)
&& ($right_context1 eq $right_context2)
&& ($in_lang_codes1 eq $in_lang_codes2)
&& ($out_lang_codes1 eq $out_lang_codes2)) {
$n_cost_rules++;
$cost_rule_id = $n_cost_rules;
$ht{COST}->{$lang_code2}->{$lang_code1}->{$s2}->{$s1}->{$cost_rule_id} = $cost;
$ht{LEFT1}->{$cost_rule_id} = $left_context2;
$ht{LEFT2}->{$cost_rule_id} = $left_context1;
$ht{RIGHT1}->{$cost_rule_id} = $right_context2;
$ht{RIGHT2}->{$cost_rule_id} = $right_context1;
$ht{INLC1}->{$cost_rule_id} = $in_lang_codes2;
$ht{INLC2}->{$cost_rule_id} = $in_lang_codes1;
$ht{OUTLC1}->{$cost_rule_id} = $out_lang_codes2;
$ht{OUTLC2}->{$cost_rule_id} = $out_lang_codes1;
# print STDERR " Flip rule in line $line: $line\n";
}
$this->rule_string_expansion(*ht, $s1, $lang_code1);
$this->rule_string_expansion(*ht, $s2, $lang_code2);
}
}
}
close(IN);
print STDERR "Read in $n_cost_rules rules from $line_number lines in $filename\n" if $verbose;
}
sub romanized_string_to_simple_chart {
local($this, $s, *chart_ht) = @_;
my @characters = $utf8->split_into_utf8_characters($s, "return only chars, return trailing whitespaces", *dummy_ht);
$chart_ht{N_CHARS} = $#characters + 1;
$chart_ht{N_NODES} = 0;
foreach $i ((0 .. $#characters)) {
$romanizer->add_node($characters[$i], $i, ($i+1), *chart_ht, "", "");
}
}
sub linearize_chart_points {
local($this, *chart_ht, $chart_id, *sd_ht, $verbose) = @_;
$verbose = 0 unless defined($verbose);
print STDERR "Linearize $chart_id\n" if $verbose;
my $current_chart_pos = 0;
my $current_linear_chart_pos = 0;
$sd_ht{POS2LINPOS}->{$chart_id}->{$current_chart_pos} = $current_linear_chart_pos;
$sd_ht{LINPOS2POS}->{$chart_id}->{$current_linear_chart_pos} = $current_chart_pos;
print STDERR " LINPOS2POS.$chart_id LIN: $current_linear_chart_pos POS: $current_chart_pos\n" if $verbose;
my @end_chart_positions = keys %{$chart_ht{NODES_ENDING_AT}};
my $end_chart_pos = (@end_chart_positions) ? max(@end_chart_positions) : 0;
$sd_ht{MAXPOS}->{$chart_id} = $end_chart_pos;
print STDERR " Chart span: $current_chart_pos-$end_chart_pos\n" if $verbose;
while ($current_chart_pos < $end_chart_pos) {
my @node_ids = keys %{$chart_ht{NODES_STARTING_AT}->{$current_chart_pos}};
foreach $node_id (@node_ids) {
my $roman_s = $chart_ht{NODE_ROMAN}->{$node_id};
my @roman_chars = $utf8->split_into_utf8_characters($roman_s, "return only chars, return trailing whitespaces", *dummy_ht);
print STDERR " $current_chart_pos/$current_linear_chart_pos node: $node_id $roman_s (@roman_chars)\n" if $verbose;
if ($#roman_chars >= 1) {
foreach $i ((1 .. $#roman_chars)) {
$current_linear_chart_pos++;
$sd_ht{SPLITPOS2LINPOS}->{$chart_id}->{$current_chart_pos}->{$node_id}->{$i} = $current_linear_chart_pos;
$sd_ht{LINPOS2SPLITPOS}->{$chart_id}->{$current_linear_chart_pos}->{$current_chart_pos}->{$node_id}->{$i} = 1;
print STDERR " LINPOS2SPLITPOS.$chart_id LIN: $current_linear_chart_pos POS: $current_chart_pos NODE: $node_id I: $i\n" if $verbose;
}
}
}
$current_chart_pos++;
if ($util->member($current_chart_pos, @end_chart_positions)) {
$current_linear_chart_pos++;
$sd_ht{POS2LINPOS}->{$chart_id}->{$current_chart_pos} = $current_linear_chart_pos;
$sd_ht{LINPOS2POS}->{$chart_id}->{$current_linear_chart_pos} = $current_chart_pos;
print STDERR " LINPOS2POS.$chart_id LIN: $current_linear_chart_pos POS: $current_chart_pos\n" if $verbose;
}
}
$current_chart_pos = 0;
while ($current_chart_pos <= $end_chart_pos) {
my $current_linear_chart_pos = $sd_ht{POS2LINPOS}->{$chart_id}->{$current_chart_pos};
$current_linear_chart_pos = "?" unless defined($current_linear_chart_pos);
my @node_ids = keys %{$chart_ht{NODES_STARTING_AT}->{$current_chart_pos}};
# print STDERR " LINROM.$chart_id LIN: $current_linear_chart_pos POS: $current_chart_pos NODES: @node_ids\n" if $verbose;
foreach $node_id (@node_ids) {
my $end_pos = $chart_ht{NODE_END}->{$node_id};
my $end_linpos = $sd_ht{POS2LINPOS}->{$chart_id}->{$end_pos};
my $roman_s = $chart_ht{NODE_ROMAN}->{$node_id};
my @roman_chars = $utf8->split_into_utf8_characters($roman_s, "return only chars, return trailing whitespaces", *dummy_ht);
print STDERR " LINROM.$chart_id LIN: $current_linear_chart_pos POS: $current_chart_pos NODE: $node_id CHARS: @roman_chars\n" if $verbose;
if (@roman_chars) {
foreach $i ((0 .. $#roman_chars)) {
my $from_linear_chart_pos
= (($i == 0)
? $sd_ht{POS2LINPOS}->{$chart_id}->{$current_chart_pos}
: $sd_ht{SPLITPOS2LINPOS}->{$chart_id}->{$current_chart_pos}->{$node_id}->{$i});
print STDERR " FROM.$chart_id I: $i POS: $current_chart_pos NODE: $node_id FROM: $from_linear_chart_pos\n" if $verbose;
my $to_linear_chart_pos
= (($i == $#roman_chars)
? $end_linpos
: $sd_ht{SPLITPOS2LINPOS}->{$chart_id}->{$current_chart_pos}->{$node_id}->{($i+1)});
print STDERR " TO.$chart_id I: $i POS: $current_chart_pos NODE: $node_id FROM: $to_linear_chart_pos\n" if $verbose;
my $roman_char = $roman_chars[$i];
$sd_ht{LIN_IJ_ROMAN}->{$chart_id}->{$from_linear_chart_pos}->{$to_linear_chart_pos}->{$roman_char} = 1;
}
} else {
my $from_linear_chart_pos = $sd_ht{POS2LINPOS}->{$chart_id}->{$current_chart_pos};
my $to_linear_chart_pos = $sd_ht{POS2LINPOS}->{$chart_id}->{($current_chart_pos+1)};
# HHERE check this out
my $i = 1;
while (! (defined($to_linear_chart_pos))) {
$i++;
$to_linear_chart_pos = $sd_ht{POS2LINPOS}->{$chart_id}->{($current_chart_pos+$i)};
}
if (defined($from_linear_chart_pos) && defined($to_linear_chart_pos)) {
$sd_ht{LIN_IJ_ROMAN}->{$chart_id}->{$from_linear_chart_pos}->{$to_linear_chart_pos}->{""} = 1
} else {
print STDERR " UNDEF.$chart_id from: "
. ((defined($from_linear_chart_pos)) ? $from_linear_chart_pos : "?")
. " to: "
. ((defined($to_linear_chart_pos)) ? $to_linear_chart_pos : "?")
. "\n";
}
}
}
$current_chart_pos++;
}
$sd_ht{MAXLINPOS}->{$chart_id} = $sd_ht{POS2LINPOS}->{$chart_id}->{$end_chart_pos};
}
sub expand_lin_ij_roman {
local($this, *sd_ht, $chart_id, $lang_code, *ht) = @_;
foreach $start (sort { $a <=> $b } keys %{$sd_ht{LIN_IJ_ROMAN}->{$chart_id}}) {
foreach $end (sort { $a <=> $b } keys %{$sd_ht{LIN_IJ_ROMAN}->{$chart_id}->{$start}}) {
foreach $roman (sort keys %{$sd_ht{LIN_IJ_ROMAN}->{$chart_id}->{$start}->{$end}}) {
if ($ht{RULE_STRING_HAS_EXPANSION}->{$lang_code}->{$roman}
|| $ht{RULE_STRING_HAS_EXPANSION}->{""}->{$roman}) {
$this->expand_lin_ij_roman_rec(*sd_ht, $chart_id, $start, $end, $roman, $lang_code, *ht);
}
}
}
}
}
sub expand_lin_ij_roman_rec {
local($this, *sd_ht, $chart_id, $start, $end, $roman, $lang_code, *ht) = @_;
# print STDERR " expand_lin_ij_roman_rec.$chart_id $start-$end $lang_code $roman\n";
return unless $ht{RULE_STRING_HAS_EXPANSION}->{$lang_code}->{$roman}
|| $ht{RULE_STRING_HAS_EXPANSION}->{""}->{$roman};
foreach $new_end (keys %{$sd_ht{LIN_IJ_ROMAN}->{$chart_id}->{$end}}) {
foreach $next_roman (sort keys %{$sd_ht{LIN_IJ_ROMAN}->{$chart_id}->{$end}->{$new_end}}) {
my $exp_roman = join("", $roman, $next_roman);
if ($ht{RULE_STRING}->{$lang_code}->{$exp_roman}
|| $ht{RULE_STRING}->{""}->{$exp_roman}) {
$sd_ht{LIN_IJ_ROMAN}->{$chart_id}->{$start}->{$new_end}->{$exp_roman} = 1;
# print STDERR " Expansion ($start-$new_end) $exp_roman\n";
}
if ($ht{RULE_STRING_HAS_EXPANSION}->{$lang_code}->{$exp_roman}
|| $ht{RULE_STRING_HAS_EXPANSION}->{""}->{$exp_roman}) {
$this->expand_lin_ij_roman_rec(*sd_ht, $chart_id, $start, $new_end, $exp_roman, $lang_code, *ht);
}
}
}
}
sub trace_string_distance {
local($this, *sd_ht, $chart1_id, $chart2_id, $control, $line_number, $cost) = @_;
my $chart_comb_id = join("/", $chart1_id, $chart2_id);
return "mismatch" if $sd_ht{MISMATCH}->{$chart_comb_id};
my $chart1_end = $sd_ht{MAXLINPOS}->{$chart1_id};
my $chart2_end = $sd_ht{MAXLINPOS}->{$chart2_id};
my $verbose = ($control =~ /verbose/);
my $chunks_p = ($control =~ /chunks/);
my @traces = ();
my @s1_s = ();
my @s2_s = ();
my @e1_s = ();
my @e2_s = ();
my @r1_s = ();
my @r2_s = ();
my @ic_s = ();
# print STDERR "trace_string_distance $chart1_id $chart2_id $line_number\n";
while ($chart1_end || $chart2_end) {
my $incr_cost = $sd_ht{INCR_COST_IJ}->{$chart_comb_id}->{$chart1_end}->{$chart2_end};
my $prec_i = $sd_ht{PREC_I}->{$chart_comb_id}->{$chart1_end}->{$chart2_end};
my $prec_j = $sd_ht{PREC_J}->{$chart_comb_id}->{$chart1_end}->{$chart2_end};
if ($incr_cost || $verbose || $chunks_p) {
my $roman1 = $sd_ht{ROMAN1}->{$chart_comb_id}->{$chart1_end}->{$chart2_end};
my $roman2 = $sd_ht{ROMAN2}->{$chart_comb_id}->{$chart1_end}->{$chart2_end};
if ($verbose) {
push(@traces, "$prec_i-$chart1_end/$prec_j-$chart2_end:$roman1/$roman2:$incr_cost");
} else {
if (defined($roman1)) {
push(@traces, "$roman1/$roman2:$incr_cost");
} else {
$print_prec_i = (defined($prec_i)) ? $prec_i : "?";
$print_prec_j = (defined($prec_j)) ? $prec_j : "?";
print STDERR " $prec_i-$chart1_end, $prec_j-$chart2_end\n";
}
}
if ($chunks_p) {
push(@s1_s, $prec_i);
push(@s2_s, $prec_j);
push(@e1_s, $chart1_end);
push(@e2_s, $chart2_end);
push(@r1_s, $roman1);
push(@r2_s, $roman2);
push(@ic_s, $incr_cost);
}
}
$chart1_end = $prec_i;
$chart2_end = $prec_j;
}
if ($chunks_p) {
my $r1 = "";
my $r2 = "";
my $tc = 0;
my $in_chunk = 0;
foreach $i ((0 .. $#ic_s)) {
if ($ic_s[$i]) {
$r1 = $r1_s[$i] . $r1;
$r2 = $r2_s[$i] . $r2;
$tc += $ic_s[$i];
$in_chunk = 1;
} elsif ($in_chunk) {
$chunk = "$r1/$r2/$tc";
$chunk .= "*" if $cost > 5;
$sd_ht{N_COST_CHUNK}->{$chunk} = ($sd_ht{N_COST_CHUNK}->{$chunk} || 0) + 1;
$sd_ht{EX_COST_CHUNK}->{$chunk}->{$line_number} = 1;
$r1 = "";
$r2 = "";
$tc = 0;
$in_chunk = 0;
}
}
if ($in_chunk) {
$chunk = "$r1/$r2/$tc";
$chunk .= "*" if $cost > 5;
$sd_ht{N_COST_CHUNK}->{$chunk} = ($sd_ht{N_COST_CHUNK}->{$chunk} || 0) + 1;
$sd_ht{EX_COST_CHUNK}->{$chunk}->{$line_number} = 1;
}
} else {
return join(" ", reverse @traces);
}
}
sub right_context_match {
local($this, $right_context_rule, *sd_ht, $chart_id, $start_pos) = @_;
return 1 if $right_context_rule eq "";
if (($right_context_item, $right_context_rest) = ($right_context_rule =~ /^\[([^\[\]]*)\]*(.*)$/)) {
my $guarded_right_context_item = $right_context_item;
$guarded_right_context_item =~ s/\$/\\\$/g;
my @end_positions = keys %{$sd_ht{LIN_IJ_ROMAN}->{$chart_id}->{$start_pos}};
return 1 if ($#end_positions == -1)
&& (($right_context_item eq "")
|| ($right_context_item =~ /\$/));
foreach $end_pos (@end_positions) {
my @romans = keys %{$sd_ht{LIN_IJ_ROMAN}->{$chart_id}->{$start_pos}->{$end_pos}};
foreach $roman (@romans) {
if ($roman =~ /^[$guarded_right_context_item]/) {
return $this->right_context_match($right_context_rest, *sd_ht, $chart_id, $end_pos);
}
}
}
}
return 0;
}
sub string_distance {
local($this, *sd_ht, $chart1_id, $chart2_id, $lang_code1, $lang_code2, *ht, $control) = @_;
my $verbose = ($control =~ /verbose/i);
my $chart_comb_id = join("/", $chart1_id, $chart2_id);
my $chart1_end_pos = $sd_ht{MAXLINPOS}->{$chart1_id};
my $chart2_end_pos = $sd_ht{MAXLINPOS}->{$chart2_id};
print STDERR "string_distance.$chart_comb_id $chart1_end_pos/$chart2_end_pos\n" if $verbose;
$sd_ht{COST_IJ}->{$chart_comb_id}->{0}->{0} = 0;
$sd_ht{COMB_LEFT_ROMAN1}->{$chart_comb_id}->{0}->{0} = "";
$sd_ht{COMB_LEFT_ROMAN2}->{$chart_comb_id}->{0}->{0} = "";
# HHERE
foreach $chart1_start ((0 .. $chart1_end_pos)) {
# print STDERR " C1 $chart1_start- ($chart1_start .. $chart1_end_pos)\n";
my $prev_further_expansion_possible = 0;
my @chart1_ends = sort { $a <=> $b } keys %{$sd_ht{LIN_IJ_ROMAN}->{$chart1_id}->{$chart1_start}};
my $max_chart1_ends = (@chart1_ends) ? $chart1_ends[$#chart1_ends] : -1;
foreach $chart1_end (($chart1_start .. $chart1_end_pos)) {
my $further_expansion_possible = ($chart1_start == $chart1_end)
|| defined($sd_ht{LINPOS2SPLITPOS}->{$chart1_id}->{$chart1_start})
|| ($chart1_end < $max_chart1_ends);
my @romans1 = (($chart1_start == $chart1_end)
? ("")
: (sort keys %{$sd_ht{LIN_IJ_ROMAN}->{$chart1_id}->{$chart1_start}->{$chart1_end}}));
if ($#romans1 == -1) {
$further_expansion_possible = 1 if $prev_further_expansion_possible;
} else {
$prev_further_expansion_possible = 0;
}
# print STDERR " C1 $chart1_start-$chart1_end romans1: @romans1 {$further_expansion_possible} *l*\n";
foreach $roman1 (@romans1) {
# print STDERR " C1 $chart1_start-$chart1_end $roman1 {$further_expansion_possible} *?*\n";
next unless $ht{RULE_STRING}->{$lang_code1}->{$roman1}
|| $ht{RULE_STRING}->{""}->{$roman1};
# print STDERR " C1 $chart1_start-$chart1_end $roman1 {$further_expansion_possible} ***\n";
foreach $lang_code1o (($lang_code1, "")) {
foreach $lang_code2o (($lang_code2, "")) {
my @chart2_starts = (sort { $a <=> $b } keys %{$sd_ht{COST_IJ}->{$chart_comb_id}->{$chart1_start}});
foreach $chart2_start (@chart2_starts) {
# print STDERR " C1 $chart1_start-$chart1_end $roman1 C2 $chart2_start- (@chart2_starts)\n";
foreach $chart2_end (($chart2_start .. $chart2_end_pos)) {
print STDERR " C1 $chart1_start-$chart1_end $roman1 C2 $chart2_start-$chart2_end\n";
my @romans2 = (($chart2_start == $chart2_end)
? ("")
: (sort keys %{$sd_ht{LIN_IJ_ROMAN}->{$chart2_id}->{$chart2_start}->{$chart2_end}}));
foreach $roman2 (@romans2) {
if ($roman1 eq $roman2) {
print STDERR " C1 $chart1_start-$chart1_end $roman1 C2 $chart2_start-$chart2_end $roman2 (IDENTITY)\n";
my $cost = 0;
my $preceding_cost = $sd_ht{COST_IJ}->{$chart_comb_id}->{$chart1_start}->{$chart2_start};
my $combined_cost = $preceding_cost + $cost;
my $old_cost = $sd_ht{COST_IJ}->{$chart_comb_id}->{$chart1_end}->{$chart2_end};
if ((! defined($old_cost)) || ($combined_cost < $old_cost)) {
$sd_ht{COST_IJ}->{$chart_comb_id}->{$chart1_end}->{$chart2_end} = $combined_cost;
push(@chart2_starts, $chart2_end) unless $util->member($chart2_end, @chart2_starts);
$sd_ht{PREC_I}->{$chart_comb_id}->{$chart1_end}->{$chart2_end} = $chart1_start;
$sd_ht{PREC_J}->{$chart_comb_id}->{$chart1_end}->{$chart2_end} = $chart2_start;
$sd_ht{ROMAN1}->{$chart_comb_id}->{$chart1_end}->{$chart2_end} = $roman1;
$sd_ht{ROMAN2}->{$chart_comb_id}->{$chart1_end}->{$chart2_end} = $roman2;
$sd_ht{COMB_LEFT_ROMAN1}->{$chart_comb_id}->{$chart1_end}->{$chart2_end}
= $sd_ht{COMB_LEFT_ROMAN1}->{$chart_comb_id}->{$chart1_start}->{$chart2_start} . $roman1;
$sd_ht{COMB_LEFT_ROMAN2}->{$chart_comb_id}->{$chart1_end}->{$chart2_end}
= $sd_ht{COMB_LEFT_ROMAN2}->{$chart_comb_id}->{$chart1_start}->{$chart2_start} . $roman2;
$comb_left_roman1 = $sd_ht{COMB_LEFT_ROMAN1}->{$chart_comb_id}->{$chart1_end}->{$chart2_end};
$sd_ht{INCR_COST_IJ}->{$chart_comb_id}->{$chart1_end}->{$chart2_end} = $cost;
$sd_ht{COST_RULE}->{$chart_comb_id}->{$chart1_end}->{$chart2_end} = "IDENTITY";
print STDERR " New cost $chart1_end/$chart2_end: $combined_cost (+$cost from $chart1_start/$chart2_start $roman1/$roman2)\n" if $verbose;
}
} else {
next unless $ht{RULE_STRING}->{$lang_code2o}->{$roman2};
print STDERR " C1 $chart1_start-$chart1_end $roman1 C2 $chart2_start-$chart2_end $roman2\n";
next unless defined($ht{COST}->{$lang_code1o}->{$lang_code2o}->{$roman1}->{$roman2});
my @cost_rule_ids = keys %{$ht{COST}->{$lang_code1o}->{$lang_code2o}->{$roman1}->{$roman2}};
foreach $cost_rule_id (@cost_rule_ids) {
## check whether any context requirements are satisfied
# left context rules are regular expressions
my $left_context_rule1 = $ht{LEFT1}->{$cost_rule_id};
if ($left_context_rule1) {
my $comb_left_roman1 = $sd_ht{COMB_LEFT_ROMAN1}->{$chart_comb_id}->{$chart1_start}->{$chart2_start};
if (defined($comb_left_roman1)) {
next unless $comb_left_roman1 =~ /$left_context_rule1/;
} else {
print STDERR " No comb_left_roman1 value for $chart_comb_id $chart1_start,$chart2_start\n";
}
}
my $left_context_rule2 = $ht{LEFT2}->{$cost_rule_id};
if ($left_context_rule2) {
my $comb_left_roman2 = $sd_ht{COMB_LEFT_ROMAN2}->{$chart_comb_id}->{$chart1_start}->{$chart2_start};
if (defined($comb_left_roman2)) {
next unless $comb_left_roman2 =~ /$left_context_rule2/;
} else {
print STDERR " No comb_left_roman2 value for $chart_comb_id $chart1_start,$chart2_start\n";
}
}
my $right_context_rule1 = $ht{RIGHT1}->{$cost_rule_id};
if ($right_context_rule1) {
my $match_p = $this->right_context_match($right_context_rule1, *sd_ht, $chart1_id, $chart1_end);
# print STDERR " Match?($right_context_rule1, 1, $chart1_end) = $match_p\n";
next unless $match_p;
}
my $right_context_rule2 = $ht{RIGHT2}->{$cost_rule_id};
if ($right_context_rule2) {
my $match_p = $this->right_context_match($right_context_rule2, *sd_ht, $chart2_id, $chart2_end);
# print STDERR " Match?($right_context_rule2, 2, $chart2_end) = $match_p\n";
next unless $match_p;
}
my $cost = $ht{COST}->{$lang_code1o}->{$lang_code2o}->{$roman1}->{$roman2}->{$cost_rule_id};
my $preceding_cost = $sd_ht{COST_IJ}->{$chart_comb_id}->{$chart1_start}->{$chart2_start};
my $combined_cost = $preceding_cost + $cost;
my $old_cost = $sd_ht{COST_IJ}->{$chart_comb_id}->{$chart1_end}->{$chart2_end};
if ((! defined($old_cost)) || ($combined_cost < $old_cost)) {
$sd_ht{COST_IJ}->{$chart_comb_id}->{$chart1_end}->{$chart2_end} = $combined_cost;
push(@chart2_starts, $chart2_end) unless $util->member($chart2_end, @chart2_starts);
$sd_ht{PREC_I}->{$chart_comb_id}->{$chart1_end}->{$chart2_end} = $chart1_start;
$sd_ht{PREC_J}->{$chart_comb_id}->{$chart1_end}->{$chart2_end} = $chart2_start;
$sd_ht{ROMAN1}->{$chart_comb_id}->{$chart1_end}->{$chart2_end} = $roman1;
$sd_ht{ROMAN2}->{$chart_comb_id}->{$chart1_end}->{$chart2_end} = $roman2;
$sd_ht{COMB_LEFT_ROMAN1}->{$chart_comb_id}->{$chart1_end}->{$chart2_end}
= $sd_ht{COMB_LEFT_ROMAN1}->{$chart_comb_id}->{$chart1_start}->{$chart2_start} . $roman1;
$sd_ht{COMB_LEFT_ROMAN2}->{$chart_comb_id}->{$chart1_end}->{$chart2_end}
= $sd_ht{COMB_LEFT_ROMAN2}->{$chart_comb_id}->{$chart1_start}->{$chart2_start} . $roman2;
$comb_left_roman1 = $sd_ht{COMB_LEFT_ROMAN1}->{$chart_comb_id}->{$chart1_end}->{$chart2_end};
# print STDERR " Comb-left-roman1($chart_comb_id,$chart1_end,$chart2_end) = $comb_left_roman1\n";
$sd_ht{INCR_COST_IJ}->{$chart_comb_id}->{$chart1_end}->{$chart2_end} = $cost;
$sd_ht{COST_RULE}->{$chart_comb_id}->{$chart1_end}->{$chart2_end} = $cost_rule_id;
print STDERR " New cost $chart1_end/$chart2_end: $combined_cost (+$cost from $chart1_start/$chart2_start $roman1/$roman2)\n" if $verbose;
}
}
}
}
}
}
}
}
$further_expansion_possible = 1
if $ht{RULE_STRING_HAS_EXPANSION}->{$lang_code1}->{$roman1}
|| $ht{RULE_STRING_HAS_EXPANSION}->{""}->{$roman1};
# print STDERR " further_expansion_possible: $further_expansion_possible (lc: $lang_code1 r1: $roman1) ***\n";
}
# print STDERR " last C1 $chart1_start-$chart1_end (@romans1)\n" unless $further_expansion_possible;
last unless $further_expansion_possible;
$prev_further_expansion_possible = 1 if $further_expansion_possible;
}
}
my $total_cost = $sd_ht{COST_IJ}->{$chart_comb_id}->{$chart1_end_pos}->{$chart2_end_pos};
unless (defined($total_cost)) {
$total_cost = 99.9999;
$sd_ht{MISMATCH}->{$chart_comb_id} = 1;
}
return $total_cost;
}
sub print_sd_ht {
local($this, *sd_ht, $chart1_id, $chart2_id, *OUT) = @_;
print OUT "string-distance chart:\n";
foreach $chart_id (($chart1_id, $chart2_id)) {
print OUT "SD chart $chart_id:\n";
foreach $from_linear_chart_pos (sort { $a <=> $b } keys %{$sd_ht{LIN_IJ_ROMAN}->{$chart_id}}) {
foreach $to_linear_chart_pos (sort { $a <=> $b } keys %{$sd_ht{LIN_IJ_ROMAN}->{$chart_id}->{$from_linear_chart_pos}}) {
foreach $roman_char (sort keys %{$sd_ht{LIN_IJ_ROMAN}->{$chart_id}->{$from_linear_chart_pos}->{$to_linear_chart_pos}}) {
print OUT " Lnode($from_linear_chart_pos-$to_linear_chart_pos): $roman_char\n";
}
}
}
}
}
sub print_chart_ht {
local($this, *chart_ht, *OUT) = @_;
print OUT "uroman chart:\n";
foreach $start (sort { $a <=> $b } keys %{$chart_ht{NODES_STARTING_AT}}) {
foreach $end (sort { $a <=> $b } keys %{$chart_ht{NODES_STARTING_AND_ENDING_AT}->{$start}}) {
foreach $node_id (keys %{$chart_ht{NODES_STARTING_AND_ENDING_AT}->{$start}->{$end}}) {
$roman_s = $chart_ht{NODE_ROMAN}->{$node_id};
print OUT " Node $node_id ($start-$end): $roman_s\n";
}
}
}
}
sub normalize_string {
local($this, $s) = @_;
# $s =~ s/(\xE2\x80\x8C)//g; # delete zero width non-joiner
$s =~ s/(\xE2\x80[\x93-\x94])/-/g; # en-dash, em-dash
$s =~ s/([\x00-\x7F\xC0-\xFE][\x80-\xBF]*)\1+/$1$1/g; # shorten 3 or more occurrences of same character in a row to 2
$s =~ s/[ \t]+/ /g;
return $s;
}
my $string_distance_chart_id = 0;
sub string_distance_by_chart {
local($this, $s1, $s2, $lang_code1, $lang_code2, *ht, *pinyin_ht, $control) = @_;
$control = "" unless defined($control);
%sd_ht = ();
$s1 = $this->normalize_string($s1);
my $lc_s1 = $utf8->extended_lower_case($s1);
$string_distance_chart_id++;
my $chart1_id = $string_distance_chart_id;
*chart_ht = $romanizer->romanize($lc_s1, $lang_code1, "", *ht, *pinyin_ht, 0, "return chart", $chart1_id);
$this->linearize_chart_points(*chart_ht, $chart1_id, *sd_ht);
$this->expand_lin_ij_roman(*sd_ht, $chart1_id, $lang_code1, *ht);
$s2 = $this->normalize_string($s2);
my $lc_s2 = $utf8->extended_lower_case($s2);
$string_distance_chart_id++;
my $chart2_id = $string_distance_chart_id;
*chart_ht = $romanizer->romanize($lc_s2, $lang_code2, "", *ht, *pinyin_ht, 0, "return chart", $chart2_id);
$this->linearize_chart_points(*chart_ht, $chart2_id, *sd_ht);
$this->expand_lin_ij_roman(*sd_ht, $chart2_id, $lang_code2, *ht);
my $cost = $this->string_distance(*sd_ht, $chart1_id, $chart2_id, $lang_code1, $lang_code2, *ht, $control);
return $cost;
}
my $n_quick_romanized_string_distance = 0;
sub quick_romanized_string_distance_by_chart {
local($this, $s1, $s2, *ht, $control, $lang_code1, $lang_code2) = @_;
# my $verbose = ($s1 eq "apit") && ($s2 eq "apet");
# print STDERR "Start quick_romanized_string_distance_by_chart\n";
$s1 = lc $s1;
$s2 = lc $s2;
$control = "" unless defined($control);
$lang_code1 = "" unless defined($lang_code1);
$lang_code2 = "" unless defined($lang_code2);
my $cache_p = ($control =~ /cache/);
my $total_cost;
if ($cache_p) {
$total_cost = $ht{CACHED_QRSD}->{$s1}->{$s2};
if (defined($total_cost)) {
return $total_cost;
}
}
my @lang_codes1 = ($lang_code1 eq "") ? ("") : ($lang_code1, "");
my @lang_codes2 = ($lang_code2 eq "") ? ("") : ($lang_code2, "");
my $chart1_end_pos = length($s1);
my $chart2_end_pos = length($s2);
my %sd_ht = ();
$sd_ht{COST_IJ}->{0}->{0} = 0;
foreach $chart1_start ((0 .. $chart1_end_pos)) {
foreach $chart1_end (($chart1_start .. $chart1_end_pos)) {
my $substr1 = substr($s1, $chart1_start, ($chart1_end-$chart1_start));
foreach $lang_code1o (@lang_codes1) {
foreach $lang_code2o (@lang_codes2) {
# next unless defined($ht{COST}->{$lang_code1o}->{$lang_code2o}->{$substr1});
}
}
my @chart2_starts = (sort { $a <=> $b } keys %{$sd_ht{COST_IJ}->{$chart1_start}});
foreach $chart2_start (@chart2_starts) {
foreach $chart2_end (($chart2_start .. $chart2_end_pos)) {
my $substr2 = substr($s2, $chart2_start, ($chart2_end-$chart2_start));
foreach $lang_code1o (@lang_codes1) {
foreach $lang_code2o (@lang_codes2) {
if ($substr1 eq $substr2) {
my $cost = 0;
my $preceding_cost = $sd_ht{COST_IJ}->{$chart1_start}->{$chart2_start};
if (defined($preceding_cost)) {
my $combined_cost = $preceding_cost + $cost;
my $old_cost = $sd_ht{COST_IJ}->{$chart1_end}->{$chart2_end};
if ((! defined($old_cost)) || ($combined_cost < $old_cost)) {
$sd_ht{COST_IJ}->{$chart1_end}->{$chart2_end} = $combined_cost;
push(@chart2_starts, $chart2_end) unless $util->member($chart2_end, @chart2_starts);
}
}
} else {
next unless defined($ht{COST}->{$lang_code1o}->{$lang_code2o}->{$substr1}->{$substr2});
my @cost_rule_ids = keys %{$ht{COST}->{$lang_code1o}->{$lang_code2o}->{$substr1}->{$substr2}};
my $best_cost = 99.99;
foreach $cost_rule_id (@cost_rule_ids) {
my $cost = $ht{COST}->{$lang_code1o}->{$lang_code2o}->{$substr1}->{$substr2}->{$cost_rule_id};
my $left_context_rule1 = $ht{LEFT1}->{$cost_rule_id};
next if $left_context_rule1
&& (! (substr($s1, 0, $chart1_start) =~ /$left_context_rule1/));
my $left_context_rule2 = $ht{LEFT2}->{$cost_rule_id};
next if $left_context_rule2
&& (! (substr($s2, 0, $chart2_start) =~ /$left_context_rule2/));
my $right_context_rule1 = $ht{RIGHT1}->{$cost_rule_id};
my $right_context1 = substr($s1, $chart1_end);
next if $right_context_rule1
&& (! (($right_context1 =~ /^$right_context_rule1/)
|| (($right_context_rule1 =~ /^\[[^\[\]]*\$/)
&& ($right_context1 eq ""))));
my $right_context_rule2 = $ht{RIGHT2}->{$cost_rule_id};
my $right_context2 = substr($s2, $chart2_end);
next if $right_context_rule2
&& (! (($right_context2 =~ /^$right_context_rule2/)
|| (($right_context_rule2 =~ /^\[[^\[\]]*\$/)
&& ($right_context2 eq ""))));
$best_cost = $cost if $cost < $best_cost;
my $preceding_cost = $sd_ht{COST_IJ}->{$chart1_start}->{$chart2_start};
my $combined_cost = $preceding_cost + $cost;
my $old_cost = $sd_ht{COST_IJ}->{$chart1_end}->{$chart2_end};
if ((! defined($old_cost)) || ($combined_cost < $old_cost)) {
$sd_ht{COST_IJ}->{$chart1_end}->{$chart2_end} = $combined_cost;
push(@chart2_starts, $chart2_end) unless $util->member($chart2_end, @chart2_starts);
}
}
}
}
}
}
}
}
}
$total_cost = $sd_ht{COST_IJ}->{$chart1_end_pos}->{$chart2_end_pos};
$total_cost = 99.99 unless defined($total_cost);
$ht{CACHED_QRSD}->{$s1}->{$s2} = $total_cost if $cache_p;
$n_quick_romanized_string_distance++;
return $total_cost;
}
sub get_n_quick_romanized_string_distance {
return $n_quick_romanized_string_distance;
}
1;