|
|
|
|
|
|
|
|
|
|
|
|
|
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]);
|
|
|
|
$ht{RULE_STRING_EXPANSION}->{$lang_code}->{$sub}->{$super} = 1;
|
|
$ht{RULE_STRING_HAS_EXPANSION}->{$lang_code}->{$sub} = 1;
|
|
|
|
}
|
|
}
|
|
}
|
|
|
|
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);
|
|
$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;
|
|
|
|
}
|
|
$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}};
|
|
|
|
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)};
|
|
|
|
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) = @_;
|
|
|
|
|
|
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;
|
|
|
|
}
|
|
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 = ();
|
|
|
|
|
|
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} = "";
|
|
|
|
foreach $chart1_start ((0 .. $chart1_end_pos)) {
|
|
|
|
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;
|
|
}
|
|
|
|
foreach $roman1 (@romans1) {
|
|
|
|
next unless $ht{RULE_STRING}->{$lang_code1}->{$roman1}
|
|
|| $ht{RULE_STRING}->{""}->{$roman1};
|
|
|
|
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) {
|
|
|
|
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) {
|
|
|
|
|
|
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);
|
|
|
|
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);
|
|
|
|
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};
|
|
|
|
$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};
|
|
|
|
}
|
|
|
|
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[\x93-\x94])/-/g;
|
|
$s =~ s/([\x00-\x7F\xC0-\xFE][\x80-\xBF]*)\1+/$1$1/g;
|
|
$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) = @_;
|
|
|
|
|
|
|
|
$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) {
|
|
|
|
}
|
|
}
|
|
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;
|
|
|
|
|
