#! /usr/bin/python3 # Last edited on 2026-10-30 01:13:50 by stolfi import os, sys, re from sys import stderr as err from math import inf, isfinite # import write_parsing_funcs as wpf import bencao_starps_standard_bipatterns as stdbip # For tests. def get_hit_candidates(bipat, text0, kmin0, text1, kmin1): # Returns a list {hcands} of all tuples {(k0,i0,k1,i1,pena,iv)} # such that there is some variant {bipat[iv]= (pat0,pat1,pena)} # of {bipat} such that {text[k0:i0]} matches {pat0} # and {text1[k1:i1]} matches {pat1}, with {k0>=kmin0} # and {k1>=kmin1}. hcands = [ ] text = (text0, text1) kmin = (kmin0, kmin1) nt = (len(text0), len(text1)) nv = len(bipat) for iv in range(nv): pena, pat0, pat1 = bipat[iv] pat = (re.compile(pat0), re.compile(pat1)) # !!! The {re.compile} Should go in the building of the {bitemp}. # Find all possible matches of {pat[side]} in # {text[side][kmin[side]:]}. Beware that # {pat[side]} may match overlapping segments. k_i_list = [ [], [] ] for side in 0, 1: # Match cannot start at position {nt[side]}: for k in range(kmin[side],nt[side]): if pat[side].match(text[side], pos = k): # Make sure we get all possible hits that start ar {k}: for i in range(k+1,nt[side]+1): if pat[side].fullmatch(text[side], pos = k, endpos = i): k_i_list[side].append((k,i,)) if len(k_i_list[side]) == 0: break # Now pair the possible matches in all ways: for k0, i0 in k_i_list[0]: for k1, i1 in k_i_list[1]: hcands.append((k0,i0,k1,i1,pena,iv)) return hcands # ---------------------------------------------------------------------- def test_get_hit_candidates_0(): err.write("\n\n\n") err.write(f"=== test_get_hit_candidates_0 ===========\n") bipat = ( ( 0.250, "FOO", "foo", ), # 0 ( 0.260, "F", "foo", ), # 1 ( 0.270, "OO", "foo", ), # 2 ( 0.280, "OO", "oo", ), # 3 ( 0.290, "OOF", "of", ), # 4 ) text0 = "FOOFOOFBARFOOO" kmin0 = 2 text1 = "foobarfoofoooofoo" kmin1 = 4 hcands = get_hit_candidates(bipat, text0, kmin0, text1, kmin1) hcands_exp = [ # "FOO", "foo" ( 3, 6, 6, 9, 0.250, 0 ), ( 3, 6, 9, 12, 0.250, 0 ), ( 3, 6, 14, 17, 0.250, 0 ), ( 10, 13, 6, 9, 0.250, 0 ), ( 10, 13, 9, 12, 0.250, 0 ), ( 10, 13, 14, 17, 0.250, 0 ), # "F", "foo" ( 3, 4, 6, 9, 0.260, 1 ), ( 3, 4, 9, 12, 0.260, 1 ), ( 3, 4, 14, 17, 0.260, 1 ), ( 6, 7, 6, 9, 0.260, 1 ), ( 6, 7, 9, 12, 0.260, 1 ), ( 6, 7, 14, 17, 0.260, 1 ), ( 10, 11, 6, 9, 0.260, 1 ), ( 10, 11, 9, 12, 0.260, 1 ), ( 10, 11, 14, 17, 0.260, 1 ), # "OO", "foo" ( 4, 6, 6, 9, 0.270, 2 ), ( 4, 6, 9, 12, 0.270, 2 ), ( 4, 6, 14, 17, 0.270, 2 ), ( 11, 13, 6, 9, 0.270, 2 ), ( 11, 13, 9, 12, 0.270, 2 ), ( 11, 13, 14, 17, 0.270, 2 ), ( 12, 14, 6, 9, 0.270, 2 ), ( 12, 14, 9, 12, 0.270, 2 ), ( 12, 14, 14, 17, 0.270, 2 ), # "OO", "oo" ( 4, 6, 7, 9, 0.280, 3 ), ( 4, 6, 10, 12, 0.280, 3 ), ( 4, 6, 11, 13, 0.280, 3 ), ( 4, 6, 12, 14, 0.280, 3 ), ( 4, 6, 15, 17, 0.280, 3 ), ( 11, 13, 7, 9, 0.280, 3 ), ( 11, 13, 10, 12, 0.280, 3 ), ( 11, 13, 11, 13, 0.280, 3 ), ( 11, 13, 12, 14, 0.280, 3 ), ( 11, 13, 15, 17, 0.280, 3 ), ( 12, 14, 7, 9, 0.280, 3 ), ( 12, 14, 10, 12, 0.280, 3 ), ( 12, 14, 11, 13, 0.280, 3 ), ( 12, 14, 12, 14, 0.280, 3 ), ( 12, 14, 15, 17, 0.280, 3 ), # "OOF, "of ( 4, 7, 8, 10, 0.290, 4 ), ( 4, 7, 13, 15, 0.290, 4 ), ] check_bipattern_hit_candidates(hcands, hcands_exp, text0, text1) return # ---------------------------------------------------------------------- def test_get_hit_candidates_1(): err.write("\n\n\n") err.write(f"=== test_get_hit_candidates_0 ===========\n") bipat = ( ( 0.000, '主', "daiin" ), # 0 ( 0.002, '主', "dair" ), # 1 ( 0.024, '主', "dain" ), # 2 ( 0.026, '主', "daiiin" ), # 3 ( 0.060, '主', "kaiin" ), # 4 ( 0.062, '主', "kair" ), # 5 ( 0.064, '主', "kain" ), # 6 ( 0.066, '主', "kaiiin" ), # 7 ( 0.070, '主', "laiin" ), # 8 ( 0.072, '主', "lair" ), # 9 ( 0.074, '主', "olaiin" ), # 10 ( 0.076, '主', "opail" ), # 11 ( 0.078, '主', "pail" ), # 12 ( 0.080, '主', "raiin" ), # 13 ( 0.082, '主', "rair" ), # 14 ( 0.084, '主', "rail" ), # 15 ) text0 = """ 丹雄鸡味甘微温主女人崩中漏下赤白沃补虚温中止血通神杀毒辟不祥头主杀鬼东门上者尤良 肪主耳聋肠主遗溺肶胵裹黄皮主泄利屎白主消渴伤寒寒热翮羽主下血闭鸡子主除热火疮痫痉 可作虎魄神物鸡白蠹能肥脂生平泽 """ text0 = re.sub("[ \n]", "", text0) kmin0 = 12 text1 = """ poarkeeodaiinqoairaracphheyqoeedeodyqokaiinqotedai raporairapylsheodytairoteeyoteeoolotaiinokeeyqokai inoraiiraldalsheeodaiinchsdqokeeeydairokaiinotaiin chedaiinolkallkldaindoeeokcheeoltaiinotcheedychora iinodaiinchedyotaiinalkaishdlaiinsheodokeeodyqoaii nytaiinotairchdaldydaimchdaiinockhhyysheyckhysheoq oeeolkaiinchsokoltchdysheeeyokaiinaraildycheodyoai irainokshey """ text1 = re.sub("[ \n]", "", text1) kmin1 = 20 hcands = get_hit_candidates(bipat, text0, kmin0, text1, kmin1) hcands_exp = [ ( 31, 32, 118, 123, 0.000, 0, ), ( 31, 32, 153, 158, 0.000, 0, ), ( 31, 32, 204, 209, 0.000, 0, ), ( 31, 32, 275, 280, 0.000, 0, ), ( 41, 42, 118, 123, 0.000, 0, ), ( 41, 42, 153, 158, 0.000, 0, ), ( 41, 42, 204, 209, 0.000, 0, ), ( 41, 42, 275, 280, 0.000, 0, ), ( 45, 46, 118, 123, 0.000, 0, ), ( 45, 46, 153, 158, 0.000, 0, ), ( 45, 46, 204, 209, 0.000, 0, ), ( 45, 46, 275, 280, 0.000, 0, ), ( 53, 54, 118, 123, 0.000, 0, ), ( 53, 54, 153, 158, 0.000, 0, ), ( 53, 54, 204, 209, 0.000, 0, ), ( 53, 54, 275, 280, 0.000, 0, ), ( 58, 59, 118, 123, 0.000, 0, ), ( 58, 59, 153, 158, 0.000, 0, ), ( 58, 59, 204, 209, 0.000, 0, ), ( 58, 59, 275, 280, 0.000, 0, ), ( 67, 68, 118, 123, 0.000, 0, ), ( 67, 68, 153, 158, 0.000, 0, ), ( 67, 68, 204, 209, 0.000, 0, ), ( 67, 68, 275, 280, 0.000, 0, ), ( 73, 74, 118, 123, 0.000, 0, ), ( 73, 74, 153, 158, 0.000, 0, ), ( 73, 74, 204, 209, 0.000, 0, ), ( 73, 74, 275, 280, 0.000, 0, ), ( 31, 32, 47, 51, 0.002, 1, ), ( 31, 32, 134, 138, 0.002, 1, ), ( 41, 42, 47, 51, 0.002, 1, ), ( 41, 42, 134, 138, 0.002, 1, ), ( 45, 46, 47, 51, 0.002, 1, ), ( 45, 46, 134, 138, 0.002, 1, ), ( 53, 54, 47, 51, 0.002, 1, ), ( 53, 54, 134, 138, 0.002, 1, ), ( 58, 59, 47, 51, 0.002, 1, ), ( 58, 59, 134, 138, 0.002, 1, ), ( 67, 68, 47, 51, 0.002, 1, ), ( 67, 68, 134, 138, 0.002, 1, ), ( 73, 74, 47, 51, 0.002, 1, ), ( 73, 74, 134, 138, 0.002, 1, ), ( 31, 32, 166, 170, 0.024, 2, ), ( 41, 42, 166, 170, 0.024, 2, ), ( 45, 46, 166, 170, 0.024, 2, ), ( 53, 54, 166, 170, 0.024, 2, ), ( 58, 59, 166, 170, 0.024, 2, ), ( 67, 68, 166, 170, 0.024, 2, ), ( 73, 74, 166, 170, 0.024, 2, ), ( 31, 32, 38, 43, 0.060, 4, ), ( 31, 32, 97, 102, 0.060, 4, ), ( 31, 32, 139, 144, 0.060, 4, ), ( 31, 32, 305, 310, 0.060, 4, ), ( 31, 32, 329, 334, 0.060, 4, ), ( 41, 42, 38, 43, 0.060, 4, ), ( 41, 42, 97, 102, 0.060, 4, ), ( 41, 42, 139, 144, 0.060, 4, ), ( 41, 42, 305, 310, 0.060, 4, ), ( 41, 42, 329, 334, 0.060, 4, ), ( 45, 46, 38, 43, 0.060, 4, ), ( 45, 46, 97, 102, 0.060, 4, ), ( 45, 46, 139, 144, 0.060, 4, ), ( 45, 46, 305, 310, 0.060, 4, ), ( 45, 46, 329, 334, 0.060, 4, ), ( 53, 54, 38, 43, 0.060, 4, ), ( 53, 54, 97, 102, 0.060, 4, ), ( 53, 54, 139, 144, 0.060, 4, ), ( 53, 54, 305, 310, 0.060, 4, ), ( 53, 54, 329, 334, 0.060, 4, ), ( 58, 59, 38, 43, 0.060, 4, ), ( 58, 59, 97, 102, 0.060, 4, ), ( 58, 59, 139, 144, 0.060, 4, ), ( 58, 59, 305, 310, 0.060, 4, ), ( 58, 59, 329, 334, 0.060, 4, ), ( 67, 68, 38, 43, 0.060, 4, ), ( 67, 68, 97, 102, 0.060, 4, ), ( 67, 68, 139, 144, 0.060, 4, ), ( 67, 68, 305, 310, 0.060, 4, ), ( 67, 68, 329, 334, 0.060, 4, ), ( 73, 74, 38, 43, 0.060, 4, ), ( 73, 74, 97, 102, 0.060, 4, ), ( 73, 74, 139, 144, 0.060, 4, ), ( 73, 74, 305, 310, 0.060, 4, ), ( 73, 74, 329, 334, 0.060, 4, ), ( 31, 32, 228, 233, 0.070, 8, ), ( 41, 42, 228, 233, 0.070, 8, ), ( 45, 46, 228, 233, 0.070, 8, ), ( 53, 54, 228, 233, 0.070, 8, ), ( 58, 59, 228, 233, 0.070, 8, ), ( 67, 68, 228, 233, 0.070, 8, ), ( 73, 74, 228, 233, 0.070, 8, ), ( 31, 32, 198, 203, 0.080, 13, ), ( 41, 42, 198, 203, 0.080, 13, ), ( 45, 46, 198, 203, 0.080, 13, ), ( 53, 54, 198, 203, 0.080, 13, ), ( 58, 59, 198, 203, 0.080, 13, ), ( 67, 68, 198, 203, 0.080, 13, ), ( 73, 74, 198, 203, 0.080, 13, ), ( 31, 32, 54, 58, 0.082, 14, ), ( 41, 42, 54, 58, 0.082, 14, ), ( 45, 46, 54, 58, 0.082, 14, ), ( 53, 54, 54, 58, 0.082, 14, ), ( 58, 59, 54, 58, 0.082, 14, ), ( 67, 68, 54, 58, 0.082, 14, ), ( 73, 74, 54, 58, 0.082, 14, ), ( 31, 32, 335, 339, 0.084, 15, ), ( 41, 42, 335, 339, 0.084, 15, ), ( 45, 46, 335, 339, 0.084, 15, ), ( 53, 54, 335, 339, 0.084, 15, ), ( 58, 59, 335, 339, 0.084, 15, ), ( 67, 68, 335, 339, 0.084, 15, ), ( 73, 74, 335, 339, 0.084, 15, ), ] check_bipattern_hit_candidates(hcands, hcands_exp, text0, text1) return # ---------------------------------------------------------------------- def check_bipattern_hit_candidates(hcands_cmp, hcands_exp, text0, text1): def print_cand(hc): k0, i0, k1, i1, pena, iv = hc hit0 = text0[k0:i0] hit1 = text1[k1:i1] err.write(f" ( {k0:3d} {i0:3d} {k1:3d} {i1:3d} {pena:5.3f} {iv:2d} ) # '{hit0}' -- '{hit1}'\n") # :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: nc_cmp = len(hcands_cmp) err.write(f"found {nc_cmp} hit candidates:\n") for ic in range(nc_cmp): print_cand(hcands_cmp[ic]) nc_exp = len(hcands_exp) err.write(f"expected {nc_exp} candidates\n") hcands_cmp.sort() hcands_exp.sort() kc_cmp = 0 kc_exp = 0 ok = True for ic in range(nc_cmp + nc_exp): if kc_cmp >= nc_cmp: ic_cmp = -1; ic_exp = kc_exp if kc_exp < nc_exp else -1 elif kc_exp >= nc_exp: ic_cmp = kc_cmp; ic_exp = -1 elif hcands_cmp[kc_cmp] < hcands_exp[kc_exp]: ic_cmp = kc_cmp; ic_exp = -1 elif hcands_cmp[kc_cmp] > hcands_exp[kc_exp]: ic_cmp = -1; ic_exp = kc_exp else: ic_cmp = kc_cmp; ic_exp = kc_exp if ic_cmp == -1 and ic_exp == -1: break if ic_cmp == -1: err.write("missing: "); print_cand(hcands_exp[ic_exp]); ok = False elif ic_exp == -1: err.write("extra: "); print_cand(hcands_cmp[ic_cmp]); ok = False else: assert hcands_cmp[ic_cmp] == hcands_exp[ic_exp] if ic_cmp == kc_cmp: kc_cmp += 1 if ic_exp == kc_exp: kc_exp += 1 if ok: err.write("result matched the expected one\n") else: assert False, "test failed" return # ---------------------------------------------------------------------- if len(sys.argv) > 1 and sys.argv[1] == "BPF.TEST": test_get_hit_candidates_0() test_get_hit_candidates_1()