Generating reading pairs / furigana string

furigana.py

# /// script
# requires-python = ">=3.11"
# dependencies = []
# ///

from __future__ import annotations

from dataclasses import dataclass
from functools import lru_cache
from typing import Dict, List, Mapping, Tuple

Pair = Tuple[str, str]
Parse = List[Pair]
Delimiters = Mapping[str, Tuple[str, str]]

_SPECIAL_NON_KANA = frozenset({"々", "ヶ", "ヵ", "〆"})


@dataclass(frozen=True, slots=True)
class _Run:
    start: int
    end: int
    is_kana: bool

    @property
    def length(self) -> int:
        return self.end - self.start


def _kata_to_hira(text: str) -> str:
    out: list[str] = []
    for ch in text:
        if ch in {"ヶ", "ヵ"}:
            out.append(ch)
            continue
        code = ord(ch)
        if 0x30A1 <= code <= 0x30F6:
            out.append(chr(code - 0x60))
        else:
            out.append(ch)
    return "".join(out)


def _is_kana_char(ch: str) -> bool:
    if ch in _SPECIAL_NON_KANA:
        return False
    code = ord(ch)
    return (0x3040 <= code <= 0x309F) or (0x30A0 <= code <= 0x30FF)


def _split_runs(normalized_text: str) -> list[_Run]:
    if not normalized_text:
        return []

    runs: list[_Run] = []
    start = 0
    current_is_kana = _is_kana_char(normalized_text[0])

    for i, ch in enumerate(normalized_text[1:], start=1):
        is_kana = _is_kana_char(ch)
        if is_kana != current_is_kana:
            runs.append(_Run(start=start, end=i, is_kana=current_is_kana))
            start = i
            current_is_kana = is_kana

    runs.append(_Run(start=start, end=len(normalized_text), is_kana=current_is_kana))
    return runs


@dataclass(frozen=True, slots=True)
class _Prepared:
    text: str
    reading: str
    normalized_text: str
    normalized_reading: str
    runs: Tuple[_Run, ...]

    def has_enough_reading(self) -> bool:
        """Necessary condition for any valid parse."""
        total_fixed_kana = sum(run.length for run in self.runs if run.is_kana)
        non_kana_runs = sum(1 for run in self.runs if not run.is_kana)
        return len(self.normalized_reading) >= total_fixed_kana + non_kana_runs


def _prepare(text: str, reading: str) -> _Prepared:
    if not text or not reading:
        raise ValueError(
            f"generate_furigana:text and reading must have length > 0: {text}, {reading}"
        )

    normalized_text = _kata_to_hira(text)
    normalized_reading = _kata_to_hira(reading)

    if not all(_is_kana_char(ch) for ch in normalized_reading):
        raise ValueError(f"generate_furigana:reading must be in kana: {reading}")

    return _Prepared(
        text=text,
        reading=reading,
        normalized_text=normalized_text,
        normalized_reading=normalized_reading,
        runs=tuple(_split_runs(normalized_text)),
    )


# Each alignment entry is (run_index, reading_start, reading_end).
_Alignment = Tuple[int, int, int]
_AlignmentPath = Tuple[_Alignment, ...]


def _pairs_from_alignment(prepared: _Prepared, alignment: _AlignmentPath) -> Parse:
    pairs: Parse = []
    for run_index, reading_start, reading_end in alignment:
        run = prepared.runs[run_index]
        if not run.is_kana:
            pairs.append(
                (
                    prepared.text[run.start : run.end],
                    prepared.reading[reading_start:reading_end],
                )
            )
    return pairs


def _all_alignments(prepared: _Prepared) -> Tuple[_AlignmentPath, ...]:
    if not prepared.has_enough_reading():
        return ()

    @lru_cache(maxsize=None)
    def dfs(run_index: int, reading_pos: int) -> Tuple[_AlignmentPath, ...]:
        if run_index == len(prepared.runs):
            return ((),) if reading_pos == len(prepared.normalized_reading) else ()

        run = prepared.runs[run_index]

        if run.is_kana:
            segment = prepared.normalized_text[run.start : run.end]
            segment_len = run.length
            if prepared.normalized_reading[reading_pos : reading_pos + segment_len] != segment:
                return ()
            rest = dfs(run_index + 1, reading_pos + segment_len)
            return tuple(
                (((run_index, reading_pos, reading_pos + segment_len),) + suffix)
                for suffix in rest
            )

        if run_index + 1 == len(prepared.runs):
            if reading_pos < len(prepared.normalized_reading):
                return ((((run_index, reading_pos, len(prepared.normalized_reading)),),))
            return ()

        anchor_run = prepared.runs[run_index + 1]
        anchor = prepared.normalized_text[anchor_run.start : anchor_run.end]
        max_end = len(prepared.normalized_reading) - len(anchor)

        out: list[_AlignmentPath] = []
        for reading_end in range(reading_pos + 1, max_end + 1):
            if (
                prepared.normalized_reading[reading_end : reading_end + len(anchor)]
                != anchor
            ):
                continue
            for suffix in dfs(run_index + 1, reading_end):
                out.append(((run_index, reading_pos, reading_end),) + suffix)
        return tuple(out)

    return dfs(0, 0)


def _first_alignment(
    prepared: _Prepared, *, require_min_reading_len: bool
) -> _AlignmentPath | None:
    if not prepared.has_enough_reading():
        return None

    @lru_cache(maxsize=None)
    def dfs(run_index: int, reading_pos: int) -> _AlignmentPath | None:
        if run_index == len(prepared.runs):
            return () if reading_pos == len(prepared.normalized_reading) else None

        run = prepared.runs[run_index]

        if run.is_kana:
            segment = prepared.normalized_text[run.start : run.end]
            segment_len = run.length
            if prepared.normalized_reading[reading_pos : reading_pos + segment_len] != segment:
                return None
            suffix = dfs(run_index + 1, reading_pos + segment_len)
            if suffix is None:
                return None
            return ((run_index, reading_pos, reading_pos + segment_len),) + suffix

        if run_index + 1 == len(prepared.runs):
            segment_len = len(prepared.normalized_reading) - reading_pos
            if segment_len <= 0:
                return None
            if require_min_reading_len and run.length > segment_len:
                return None
            return ((run_index, reading_pos, len(prepared.normalized_reading)),)

        anchor_run = prepared.runs[run_index + 1]
        anchor = prepared.normalized_text[anchor_run.start : anchor_run.end]
        max_end = len(prepared.normalized_reading) - len(anchor)

        for reading_end in range(reading_pos + 1, max_end + 1):
            if (
                prepared.normalized_reading[reading_end : reading_end + len(anchor)]
                != anchor
            ):
                continue
            segment_len = reading_end - reading_pos
            if require_min_reading_len and run.length > segment_len:
                continue
            suffix = dfs(run_index + 1, reading_end)
            if suffix is not None:
                return ((run_index, reading_pos, reading_end),) + suffix
        return None

    return dfs(0, 0)


def _render_furigana(
    prepared: _Prepared,
    alignment: _AlignmentPath,
    delimiters: Delimiters,
) -> str:
    ruby_open, ruby_close = delimiters["ruby"]
    rt_open, rt_close = delimiters["rt"]

    parts: list[str] = []
    cursor = 0

    for run_index, reading_start, reading_end in alignment:
        run = prepared.runs[run_index]
        if cursor < run.start:
            parts.append(prepared.text[cursor : run.start])

        segment_text = prepared.text[run.start : run.end]
        segment_reading = prepared.reading[reading_start:reading_end]

        if run.is_kana:
            parts.append(segment_text)
        else:
            parts.append(
                f"{ruby_open}{segment_text}{rt_open}{segment_reading}{rt_close}{ruby_close}"
            )

        cursor = run.end

    if cursor < len(prepared.text):
        parts.append(prepared.text[cursor:])

    return "".join(parts)


def generate_possible_kanji_reading_pairs(
    text: str,
    reading: str,
) -> List[List[Tuple[str, str]]]:
    """Return all valid non-kana reading pairings in search order.

    # ! it is impossible to always determine an unique reading from the arguments alone
    # this function generates all valid readings (fully-aligned, each kanji block mapped to at least one kana)
    # and greedily short readings of kanji are at the front of the list

    # this is a good heuristic for short text
    # (like a MeCab token, where there should not be any ambiguity in the first place)
    # but fails on e.g., 鹿乃子のこのこ虎視眈々, しかのこのこのここしたんたん
    # the valid furigana pairs returned in order are
    # 鹿乃子(しか)のこのこ虎視眈々(のここしたんたん)
    # 鹿乃子(しかのこ)のこのこ虎視眈々(こしたんたん) * correct

    # a consumer of parses can check that each kanji block is assigned kana at least as long
    # though this is again not guaranteed, and should have a fallback to the first parse
    # e.g., 蝦虎魚, はぜ

    """
    prepared = _prepare(text, reading)
    return [_pairs_from_alignment(prepared, alignment) for alignment in _all_alignments(prepared)]


def generate_furigana(
    text: str,
    reading: str,
    delimiters: Dict[str, Tuple[str, str]],
    min_reading_len: bool = True,
) -> str:
    """Render furigana using the first acceptable alignment.

    When min_reading_len is True, the function prefers the first parse where
    every emitted non-kana pair satisfies len(text_block) <= len(reading_block).
    If no such parse exists, it falls back to the first valid parse.

    Kana runs, including leading kana, are always emitted as plain text.
    """
    prepared = _prepare(text, reading)

    alignment: _AlignmentPath | None = None
    if min_reading_len:
        alignment = _first_alignment(prepared, require_min_reading_len=True)
    if alignment is None:
        alignment = _first_alignment(prepared, require_min_reading_len=False)

    if alignment is None:
        raise ValueError(
            f"generate_furigana: no valid configuration found for {text}, {reading}"
        )

    return _render_furigana(prepared, alignment, delimiters)


def _run_smoke_tests() -> None:
    delimiters = {"ruby": ("<ruby>", "</ruby>"), "rt": ("<rt>", "</rt>")}

    examples = {
        ("持ち力と届かない", "もちちからととどかない"): "<ruby>持<rt>も</rt></ruby>ち<ruby>力<rt>ちから</rt></ruby>と<ruby>届<rt>とど</rt></ruby>かない",
        ("持ち越し", "もちこし"): "<ruby>持<rt>も</rt></ruby>ち<ruby>越<rt>こ</rt></ruby>し",
        ("子", "こ"): "<ruby>子<rt>こ</rt></ruby>",
        ("朽ちる", "くちる"): "<ruby>朽<rt>く</rt></ruby>ちる",
        ("房々", "ふさふさ"): "<ruby>房々<rt>ふさふさ</rt></ruby>",
        ("蛮殻", "バンカラ"): "<ruby>蛮殻<rt>バンカラ</rt></ruby>",
        ("がぶ飲み", "がぶのみ"): "がぶ<ruby>飲<rt>の</rt></ruby>み",
        ("已んぬる哉", "やんぬるかな"): "<ruby>已<rt>や</rt></ruby>んぬる<ruby>哉<rt>かな</rt></ruby>",
        ("付きっ切り", "つきっきり"): "<ruby>付<rt>つ</rt></ruby>きっ<ruby>切<rt>き</rt></ruby>り",
        ("歯が痛いので歯科医に診てもらった", "はがいたいのでしかいにみてもらった"): "<ruby>歯<rt>は</rt></ruby>が<ruby>痛<rt>いた</rt></ruby>いので<ruby>歯科医<rt>しかい</rt></ruby>に<ruby>診<rt>み</rt></ruby>てもらった",
        ("鹿乃子のこのこ虎視眈々", "しかのこのこのここしたんたん"): "<ruby>鹿乃子<rt>しかのこ</rt></ruby>のこのこ<ruby>虎視眈々<rt>こしたんたん</rt></ruby>",
        (
            "斜め七十七度の並びで泣く泣く嘶くナナハン七台難なく並べて長眺め",
            "ななめななじゅうななどのならびでなくなくいななくななはんななだいなんなくならべてながながめ",
        ): "<ruby>斜<rt>なな</rt></ruby>め<ruby>七十七度<rt>ななじゅうななど</rt></ruby>の<ruby>並<rt>なら</rt></ruby>びで<ruby>泣<rt>な</rt></ruby>く<ruby>泣<rt>な</rt></ruby>く<ruby>嘶<rt>いなな</rt></ruby>くナナハン<ruby>七台難<rt>ななだいなん</rt></ruby>なく<ruby>並<rt>なら</rt></ruby>べて<ruby>長眺<rt>ながなが</rt></ruby>め",
        ("由比ヶ浜結衣", "ゆいがはまゆい"): "<ruby>由比ヶ浜結衣<rt>ゆいがはまゆい</rt></ruby>",
        ("雪ノ下雪乃", "ゆきのしたゆきの"): "<ruby>雪<rt>ゆき</rt></ruby>ノ<ruby>下雪乃<rt>したゆきの</rt></ruby>",
        ("蝦虎魚", "はぜ"): "<ruby>蝦虎魚<rt>はぜ</rt></ruby>",
        ("パン屋", "ぱんや"): "パン<ruby>屋<rt>や</rt></ruby>",
        ("ネ蛮ツれ", "ネざツレ"): "ネ<ruby>蛮<rt>ざ</rt></ruby>ツれ",
        ("あいう", "あいう"): "あいう",
    }

    for (text, reading), expected in examples.items():
        actual = generate_furigana(text, reading, delimiters, min_reading_len=True)
        if actual != expected:
            raise AssertionError(
                f"unexpected output for {(text, reading)}\nexpected: {expected}\nactual:   {actual}"
            )

    pair_cases = [
        ("がぶ飲み", "がぶのみ", [[("飲", "の")]]),
        ("パン屋", "ぱんや", [[("屋", "や")]]),
        ("あいう", "あいう", [[]]),
    ]
    for text, reading, expected in pair_cases:
        actual = generate_possible_kanji_reading_pairs(text, reading)
        if actual != expected:
            raise AssertionError(
                f"unexpected pair output for {(text, reading)}\nexpected: {expected}\nactual:   {actual}"
            )

    invalid = [
        ("あ亜", "あ"),
        ("パ並", "ぢぱ"),
    ]
    for text, reading in invalid:
        try:
            generate_furigana(text, reading, delimiters, min_reading_len=True)
        except ValueError:
            continue
        raise AssertionError(f"expected ValueError for {(text, reading)}")

    print("Smoke tests passed.")


def main() -> None:
    _run_smoke_tests()


if __name__ == "__main__":
    main()