#! /usr/bin/python3 # Last edited on 2026-06-30 02:26:43 by stolfi import os, sys, re from sys import stderr as err, stdout as out from math import sqrt, hypot, log, exp, floor, ceil, inf, nan, isfinite import standard_bipatterns as stdbip # For tests. import numpy as np def list_bipat_occurrences(text, utype, bipat): # Looks for matches in the given {text} of the # bipattern {bipat}. See {bitemplate_match_funcs.py} for # the definition of bipattern. # # The parameter {utype} specifies the type of {text}; it can be # "ch" (meaning that the {text} is in hanzi) or "ec" (meaning that the # {text} is in EVA). From each variant {(pena, pat0, pat1)} of {bipat}, # the pattern {pat0} or {pat1} will be used in each case, respectively. # # Let {nt} be the length of {text}. The procedure returns a list of # /hits/, one for each substring of {text} that matches the {bipat}. # Each hit is a triple {(kwpos, kword, kpena)} where # # {kwpos} is the position where the match started; that is, # the number of characters (hanzi or EVA) in{text} before the # matched substring. # # {kword} is the substring of {text} that matched. # # {kpena} is the penalty associated with the variant of # {bipat} that matched. # # debug_all = (text1[:15] == "pokararkeeyokee") # debug_all = (text1[:13] == "poarkeeodaiin") debug = True verbose = False nt = len(text); # Lengths of the text. side = None if utype == "ch": side = 0 elif utype == "ec": side = 1 else: assert False, f"invalid {utype = }" if debug: err.write(f"!~ enter list_bipat_occurrences\n") err.write(f"!~ {side = } {nt = :3d} {text = !r}\n") err.write(f"!~ {bipat = !r}\n") # Scan {bipat} and all viable substrings of {text}, setting # {seg_was_hit[it][mt]} to true iff {text[it:it+mt]} matched. mt_max = max_bipattern_hit_length(bipat, side) if debug: err.write(f" {mt_max = }\n") seg_was_hit = [ [ False ] * (mt_max+1) for it in range(nt+1) ] hits_list = [] pena_prev = None for pena, pat0, pat1 in bipat: assert pena_prev is None or pena > pens_prev, \ f"non monotonic penalties {pena_prev = } {pena = }" pat = (pat0, pat1)[side] if debug: err.write(f" {pena = :6.4f} {pat = !r}\n") # Find all occurrences of {pat} in {text}, # even overlapping (but not coincident) ones. for it in range(nt+1): for jt in range(it, min(it + mt_max, nt)+1): seg = text[it:jt] mt = jt - it; # if debug: err.write(f" {it = } {jt = } {mt = } {seg = !r}") if re.fullmatch(pat, seg) is not None: if debug: err.write(f" {it = } {jt = } {mt = } {seg = !r}") if debug: err.write(f" (matched)") if not seg_was_hit[it][mt]: seg_was_hit[it][mt] = True hits_list.append((it, seg, pena)) if debug: err.write(f" (added)") if debug: err.write(f" {it = } {jt = } {mt = } {seg = !r}") # if debug: err.write(f"\n") # Sort the hits by position: hits_list.sort(key = lambda hit: (hit[0],len(hit[1]))) if debug: err.write("!~ exit list_bipat_occurrences\n") return hits_list # ---------------------------------------------------------------------- def check_bipattern_hits(text, utype, bipat, hits_list, hits_list_exp, verbose): if verbose: err.write("checking hits ...\n") err.write(f" {hits_list = !r}\n") if hits_list_exp is not None: err.write(f" {hits_list_exp = !r}\n") assert hits_list is not None assert utype == "ch" or utype == "ec", f"invalid {utype = !r}" nt = len(text) nh = len(hits_list) side = 0 if utype == "ch" else 1 pad = '　' if utype == "ch" else " " if nh == 0 and verbose: err.write(" (no occurrences.)\n") if hits_list_exp is not None: assert nh == len(hits_list_exp), \ f"hit list length mismatch: {nh} {len(hits_list_exp)}" for ih in range(nh): kwpos, kword, kpena = hits_list[ih] assert isinstance(kword, str) assert isinstance(kpena, float) and kpena >= 0 kwend = kwpos + len(kword) assert 0 <= kwpos and kwend <= nt ok = False assert kword == text[kwpos:kwend] for apena, pat0, pat1 in bipat: pat = (pat0, pat1)[side] if re.fullmatch(pat, kword) and kpena == apena: ok = True; break if not ok: assert False, f"wrong hit {kwpos = } {kword = !r} {kpena = :6.4f}" if hits_list_exp is not None: kwpos_exp, kword_exp, kpena_exp = hits_list_exp[ih] assert kwpos == kwpos_exp, \ f"position error: {ih = } {kwpos = } expected {kwpos_exp}" assert kword == kword_exp, \ f"matched string error: {ih = } {kword = !r} expected {kword_exp!r}" assert kpena == kpena_exp, \ f"penalty error: {ih = } {kpena = :24.16e} expected {kpena_exp:24.16e}" return # ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::~ def max_pattern_hit_length(pat): # Returns an upper bound for the length of any string matched by the # (uncompiled) RE pattern {pat}. # # The pattern must use only literal characters to be matched, # character sets in '[]', alternatives with '|', and the '?' operator. # It cannot use parens '()', braces '{}', or the '*' or '+' operators, # not even escaped. It cannot use escapes # Make sure that {pat} has no funnies: assert re.search(r"[(){}+*]", pat) is None, f"bad pattern {pat = !r}" alts = pat.split('|') mt_max = 0 for alt in alts: mt_max = max(mt_max, len(alt)) return mt_max # ---------------------------------------------------------------------- def max_bipattern_hit_length(bipat, side): # Returns an upper bound for the length of any string matched by # the {side} side of any variant of the bipattern {bipat}. # # The restrictions of {} apply to the pattern on the {side} side # of every varant. mt_max = 0 for pena, pat0, pat1 in bipat: pat = (pat0,pat1)[side] mt1 = max_pattern_hit_length(pat) mt_max = max(mt_max, mt1) return mt_max # ---------------------------------------------------------------------- def test_list_bipat_occurrences(text, utype, bipat, hits_list_exp): err.write("=== testing {list_bipat_occurrences} ===\n") debug = True hits_list = list_bipat_occurrences(text, utype, bipat) check_bipattern_hits(text, utype, bipat, hits_list, hits_list_exp, verbose = True) err.write("=================================\n") return hits_list # ---------------------------------------------------------------------- def test_list_bipat_occurrences_0(): err.write(f"=== test_list_bipat_occurrences_0() ===========\n") text = "...XX........XaX..." bipat_A = ( ( 0.000, 'XX', 'YY', ), ( 0.020, 'XX', 'ZZ', ), ( 0.040, 'Xa?X', 'Za?Z', ), ) hits_list_exp = ( ( 3, "XX", 0.000), (13, "XaX", 0.040), ) hits_list = test_list_bipat_occurrences(text, "ch", bipat_A, hits_list_exp) return # ---------------------------------------------------------------------- def test_list_bipat_occurrences_1a(): err.write("\n\n\n") err.write(f"=== test_list_bipat_occurrences_1a() ===========\n") bipat_USES = stdbip.get_bencao_starps_bipattern('USES') text = \ "主杀鬼肪主耳聋肠主遗溺肶胵裹黄皮" hits_list_exp = ( (0, "主", 0.000), (4, "主", 0.000), (8, "主", 0.000), ) hits_list = test_list_bipat_occurrences(text, "ch", bipat_USES, hits_list_exp) return # ---------------------------------------------------------------------- def test_list_bipat_occurrences_1b(with_dain): err.write("\n\n\n") err.write(f"=== test_list_bipat_occurrences_1b({with_dain=!r}) ===========\n") bipat_USES = stdbip.get_bencao_starps_bipattern('USES') text = \ "daiinchsdqokeeeydaiinokaiinotaiinlaiinch" + \ "eolkallkldaindoeeokcheeoltaiiinotcheedyc" + \ "horoiino" if not with_dain: text = re.sub(r"dain", "xxxx", text) hits_list_exp = ( ( 0, "daiin", 0.000), (16, "daiin", 0.000), (22, "kaiin", 0.400), (28, "taiin", 0.800), (33, "laiin", 0.400), (49, "dain", 0.200) if with_dain else None, (65, "taiiin", 0.810), (82, "roiin", 0.600), ) hits_list_exp = tuple(( hit for hit in hits_list_exp if hit is not None )) hits_list = test_list_bipat_occurrences(text, "ec", bipat_USES, hits_list_exp) return # ---------------------------------------------------------------------- def test_list_bipat_occurrences_2a(): err.write("\n\n\n") err.write(f"=== test_list_bipat_occurrences_2a() ===========\n") bipat_LONG = stdbip.get_bencao_starps_bipattern('LONG') text = "蜂子主治风头除久食蛊毒补虚羸伤中久服令人" hits_list_exp = ( ( 7, "久食", 0.000 ), (16, "久服", 0.000 ), ) hits_list = test_list_bipat_occurrences(text, "ch", bipat_LONG, hits_list_exp) return # ---------------------------------------------------------------------- def test_list_bipat_occurrences_2b(): err.write("\n\n\n") err.write(f"=== test_list_bipat_occurrences_2b() ===========\n") bipat_LONG = stdbip.get_bencao_starps_bipattern('LONG') text = "deechdykeedykalopchedyqokaiinytchy" hits_list_exp = ( ( 6, "ykeedy", 0.150 ), ( 7, "keedy", 0.150 ), (15, "opchedy", 0.150 ), (15, "opchedyqokaiin", 0.100 ), (16, "pchedy", 0.150 ), (16, "pchedyqokaiin", 0.100 ), (22, "qokaiin", 0.050 ), (23, "okaiin", 0.050 ), ) hits_list = test_list_bipat_occurrences(text, "ec", bipat_LONG, hits_list_exp) return # ---------------------------------------------------------------------- if len(sys.argv) > 1 and sys.argv[1] == "BPF.TEST": test_list_bipat_occurrences_0() test_list_bipat_occurrences_1a() test_list_bipat_occurrences_1b(with_dain = False) test_list_bipat_occurrences_1b(with_dain = True) test_list_bipat_occurrences_2a() test_list_bipat_occurrences_2b()