99 lines
3.2 KiB
Python
99 lines
3.2 KiB
Python
"""Proportional analogy: solve a : b :: c : x at the string level.
|
|
|
|
Used for (1) generating unseen inflected forms from paradigm neighbors and
|
|
(2) the chrF-floor fallback. Transformation model: a -> b is a prefix and/or
|
|
suffix replacement around a shared core, which covers concatenative
|
|
morphology. The same edit is applied to c. All consistent answers are
|
|
returned, ranked by preserved stem material.
|
|
"""
|
|
|
|
from __future__ import annotations
|
|
|
|
from collections import Counter
|
|
from typing import List, Optional, Tuple
|
|
|
|
# A rule is (a_pre, b_pre, a_suf, b_suf): replace prefix a_pre with b_pre and
|
|
# suffix a_suf with b_suf.
|
|
Rule = Tuple[str, str, str, str]
|
|
|
|
|
|
def _lcp(a: str, b: str) -> int:
|
|
i = 0
|
|
while i < min(len(a), len(b)) and a[i] == b[i]:
|
|
i += 1
|
|
return i
|
|
|
|
|
|
def _lcsuf(a: str, b: str) -> int:
|
|
i = 0
|
|
while i < min(len(a), len(b)) and a[-1 - i] == b[-1 - i]:
|
|
i += 1
|
|
return i
|
|
|
|
|
|
def edit_rules(a: str, b: str) -> List[Rule]:
|
|
"""Candidate decompositions of the transformation a -> b."""
|
|
rules: List[Rule] = []
|
|
p = _lcp(a, b)
|
|
s = _lcsuf(a, b)
|
|
if p > 0:
|
|
rules.append(("", "", a[p:], b[p:])) # keep shared prefix, swap suffix
|
|
if s > 0:
|
|
rules.append((a[: len(a) - s], b[: len(b) - s], "", "")) # swap prefix
|
|
if p > 0 and s > 0 and p + s <= min(len(a), len(b)):
|
|
# circumfix-ish: shared prefix AND suffix, swap the middle — model as
|
|
# suffix swap on the part after the shared prefix
|
|
rules.append(("", "", a[p : len(a) - s], b[p : len(b) - s]))
|
|
if not rules:
|
|
rules.append((a, b, "", "")) # suppletion: whole-string replacement
|
|
return rules
|
|
|
|
|
|
def apply_rule(rule: Rule, c: str) -> Optional[str]:
|
|
a_pre, b_pre, a_suf, b_suf = rule
|
|
out = c
|
|
if a_pre and not out.startswith(a_pre):
|
|
return None
|
|
out = b_pre + out[len(a_pre):]
|
|
if a_suf:
|
|
if not out.endswith(a_suf):
|
|
return None
|
|
out = out[: len(out) - len(a_suf)] + b_suf
|
|
else:
|
|
out = out + b_suf
|
|
return out
|
|
|
|
|
|
def apply_rule_mid(rule: Rule, c: str) -> Optional[str]:
|
|
"""Apply a middle-swap rule (encoded as suffix-swap) as an infix
|
|
substitution when the plain application fails: replace the last
|
|
occurrence of a_suf inside c."""
|
|
_, _, a_mid, b_mid = rule
|
|
if not a_mid or a_mid not in c:
|
|
return None
|
|
i = c.rfind(a_mid)
|
|
return c[:i] + b_mid + c[i + len(a_mid):]
|
|
|
|
|
|
def solve(a: str, b: str, c: str) -> List[str]:
|
|
"""Candidate solutions x to a : b :: c : x, best first."""
|
|
scored: Counter = Counter()
|
|
for rule in edit_rules(a, b):
|
|
x = apply_rule(rule, c)
|
|
if x is None:
|
|
x = apply_rule_mid(rule, c)
|
|
if x:
|
|
stem_kept = len(c) - len(rule[0]) - len(rule[2])
|
|
scored[x] = max(scored[x], stem_kept)
|
|
return [w for w, _ in scored.most_common()]
|
|
|
|
|
|
def solve_from_pairs(pairs: List[Tuple[str, str]], c: str) -> List[str]:
|
|
"""Given attested (form_a, form_b) pairs exhibiting one transformation,
|
|
vote for the best x completing c : x under that transformation."""
|
|
votes: Counter = Counter()
|
|
for a, b in pairs:
|
|
for rank, x in enumerate(solve(a, b, c)):
|
|
votes[x] += 1.0 / (1 + rank)
|
|
return [w for w, _ in votes.most_common()]
|