| 1 | package Peta::NN::Codec; | ||
| 2 | # ABSTRACT: characters to token indices, string pairs to edit labels | ||
| 3 | |||
| 4 | # Between strings and what a network eats and emits: characters become token | ||
| 5 | # indices through a vocabulary, and a pair of strings becomes an edit label. | ||
| 6 | |||
| 7 | use v5.36; | ||
| 8 | |||
| 9 | use Exporter 'import'; | ||
| 10 | |||
| 11 | our $VERSION = '0.2610090'; | ||
| 12 | our @EXPORT_OK = qw(build_vocab window edit_label apply_edit edit2_label apply_edit2 PAD UNKNOWN); | ||
| 13 | |||
| 14 | # Two indices are reserved: a window reaching past either end of the string | ||
| 15 | # reads PAD there, and a character never seen in training reads UNKNOWN. | ||
| 16 | use constant { PAD => 0, UNKNOWN => 1 }; | ||
| 17 | |||
| 18 | my $FIRST_CHAR_INDEX = 2; | ||
| 19 | |||
| 20 | # { character => index } over every character of the given strings. | ||
| 21 | sub build_vocab ($strings) { | ||
| 22 | my %seen; | ||
| 23 | for my $string (@$strings) { | ||
| 24 | $seen{$_} = 1 for split //, $string; | ||
| 25 | } | ||
| 26 | my $index = $FIRST_CHAR_INDEX; | ||
| 27 | return { map { $_ => $index++ } sort keys %seen }; | ||
| 28 | } | ||
| 29 | |||
| 30 | # The token indices of $count consecutive positions of @$chars starting at | ||
| 31 | # $from, which may lie before the start or run past the end. Every window in | ||
| 32 | # this library is this one shape: the last n characters start at length - n, | ||
| 33 | # the first n at 0, and n either side of position p at p - n. | ||
| 34 | sub window ($chars, $from, $count, $vocab) { | ||
| 35 | return [ | ||
| 36 | map { $_ < 0 || $_ > $#$chars ? PAD : $vocab->{ $chars->[$_] } // UNKNOWN } | ||
| 37 | $from .. $from + $count - 1 | ||
| 38 | ]; | ||
| 39 | } | ||
| 40 | |||
| 41 | # How to turn $in into $out by rewriting its end: "cut:add" says drop that | ||
| 42 | # many characters and append that text. Jelínek -> Jelínku is "2:ku". Many | ||
| 43 | # words share one label, which is what makes it learnable as a class. | ||
| 44 | sub edit_label ($in, $out) { | ||
| 45 | my $common = 0; | ||
| 46 | my $limit = length $in < length $out ? length $in : length $out; | ||
| 47 | $common++ while $common < $limit && substr($in, $common, 1) eq substr($out, $common, 1); | ||
| 48 | return (length($in) - $common) . ':' . substr($out, $common); | ||
| 49 | } | ||
| 50 | |||
| 51 | # Undefined when the label asks to cut more than the string has. | ||
| 52 | sub apply_edit ($in, $label) { | ||
| 53 | my ($cut, $add) = split /:/, $label, 2; | ||
| 54 | return if $cut > length $in; | ||
| 55 | return substr($in, 0, length($in) - $cut) . $add; | ||
| 56 | } | ||
| 57 | |||
| 58 | # The longest stretch of characters two strings share: where it starts in | ||
| 59 | # each, and how long it is. Of several equally long, the first in $in. | ||
| 60 | sub _common ($in, $out) { | ||
| 61 | my @a = split //, $in; | ||
| 62 | my @b = split //, $out; | ||
| 63 | my ($best, $at_in, $at_out) = (0, 0, 0); | ||
| 64 | my @run = (0) x (@b + 1); # $run[j]: length of the stretch ending at a[i-1], b[j-1] | ||
| 65 | for my $i (1 .. @a) { | ||
| 66 | my @next = (0) x (@b + 1); | ||
| 67 | for my $j (1 .. @b) { | ||
| 68 | next if $a[ $i - 1 ] ne $b[ $j - 1 ]; | ||
| 69 | my $length = $next[$j] = $run[ $j - 1 ] + 1; | ||
| 70 | ($best, $at_in, $at_out) = ($length, $i - $length, $j - $length) if $length > $best; | ||
| 71 | } | ||
| 72 | @run = @next; | ||
| 73 | } | ||
| 74 | return ($at_in, $at_out, $best); | ||
| 75 | } | ||
| 76 | |||
| 77 | # How to turn $in into $out by rewriting BOTH ends around what they share: | ||
| 78 | # "cut:add|cut:add", first for the front, then for the end. chytrý -> | ||
| 79 | # nejchytřejší keeps "chyt" and is "0:nej|2:řejší". | ||
| 80 | sub edit2_label ($in, $out) { | ||
| 81 | my ($at_in, $at_out, $length) = _common($in, $out); | ||
| 82 | return "$at_in:" . substr($out, 0, $at_out) . '|' | ||
| 83 | . (length($in) - $at_in - $length) . ':' . substr($out, $at_out + $length); | ||
| 84 | } | ||
| 85 | |||
| 86 | # Undefined when the label asks to cut more than the string has. | ||
| 87 | sub apply_edit2 ($in, $label) { | ||
| 88 | my ($front, $back) = split /\|/, $label, 2; | ||
| 89 | my ($cut_front, $add_front) = split /:/, $front, 2; | ||
| 90 | my ($cut_back, $add_back) = split /:/, $back, 2; | ||
| 91 | return if $cut_front + $cut_back > length $in; | ||
| 92 | return $add_front . substr($in, $cut_front, length($in) - $cut_front - $cut_back) . $add_back; | ||
| 93 | } | ||
| 94 | |||
| 95 | 1; | ||
| 96 | |||
| 97 | __END__ |