#! /usr/bin/python3 # Last edited on 2026-10-30 13:08:37 by stolfi import os, sys, re from sys import stderr as err from math import inf, isfinite # import write_parsing_funcs as wpf import bipattern_funcs as bpf import bencao_starps_standard_bipatterns as stdbip # For tests. def get_hit_candidate_lists(bitemp, text0, text1): # Returns lists hcand_lists[0..nh-1]} with the index intervals or substrings # of {text0} and {text1} that match the bipatterns in {bitemp}. # # Specifically, for each bipat {bitemp[ih]}, # {hcand_lists[ih]} is a list of all tuples {(k0,i0,k1,i1,pena,iv)} # {text0[k0:i0]} matches {pat0} and {text0[k1:i1]} for some variant {iv} # {(pat0,pat1,pena)} of the bipattern {bitemp[ih]}. # # Assumes that hits cannot be empty. # # Eilther every list has at least one candidate, or all lists are empty. # In the latter case the procedure returns None. debug = True nt0 = len(text0); nt1 = len(text1) hcand_lists = [ ] nh = len(bitemp) kmin = [ 0, 0, ] text = ( text0, text1 ) for ih in range(nh): bipat = bitemp[ih] nv = len(bipat); if debug: err.write(f"!b getting cands for hit {ih} {kmin = !r} ...") hcands = bpf.get_hit_candidates(bipat, text0, kmin[0], text1, kmin[1]) if debug: err.write(f" found {len(hcands)}.\n") hcand_lists.append(hcands) kmin = [ nt0+1, nt1+1, ] for k0, i0, k1, i1, pena, iv in hcands: if i0 < kmin[0]: kmin[0] = i0 if i1 < kmin[1]: kmin[1] = i1 # Now trim each list based on min match of subsequent hits: imax = [ nt0, nt1 ] for ih in range(nh-1, -1, -1): if debug: err.write(f"!b trimming cands for hit {ih} {imax = !r} ...") hcands = [ hc for hc in hcand_lists[ih] if hc[1] <= imax[0] and hc[3] <= imax[1] ] if debug: err.write(f" left {len(hcands)}.\n") hcand_lists[ih] = hcands imax = [ 0, 0 ] for k0,i0,k1,i1,pena,iv in hcands: if k0 > imax[0]: imax[0] = k0 if k1 > imax[1]: imax[1] = k1 # Check for failure: nok = 0 for hcands in hcand_lists: if len(hcands) > 0: nok += 1 if nok == 0: # Failure: hcand_lists = None else: if debug: err.write(f"!b total {nok} non-empty lists.\n") assert nok == nh return hcand_lists # ---------------------------------------------------------------------- def check_bitemplate_hit_candidate_lists(hcand_lists_cmp, hcand_lists_exp, text0, text1): nh = len(hcand_lists_exp) assert len(hcand_lists_cmp) == nh for ih in range(nh): err.write(f"checking lists for hit {ih} ...\n") bpf.check_bipattern_hit_candidates(hcand_lists_cmp[ih], hcand_lists_exp[ih], text0, text1) err.write("result matched the expected one\n") return # ---------------------------------------------------------------------- def test_get_hit_candidate_lists_0(): err.write("\n\n\n") err.write(f"=== test_get_hit_candidates_0 ===========\n") text0 = "FOOFOOFBARFOOO" text1 = "oofoobarfoofoooofoo" bipatA = ( ( 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 ) bipatB = ( ( 0.300, "BAR", "bar", ), # 0 ( 0.310, "AR", "ba", ), # 1 ( 0.320, "AR", "ar", ), # 2 ) bitemp = ( bipatA, bipatB, bipatA, ) hcand_lists = get_hit_candidate_lists(bitemp, text0, text1) hcand_lists_exp = [ None ]*3 hcand_lists_exp[0] = [ # "FOO", "foo" ( 0, 3, 2, 5, 0.250, 0 ), ( 3, 6, 2, 5, 0.250, 0 ), # "F", "foo" ( 0, 1, 2, 5, 0.260, 1 ), ( 3, 4, 2, 5, 0.260, 1 ), ( 6, 7, 2, 5, 0.260, 1 ), # "OO", "foo" ( 1, 3, 2, 5, 0.270, 2 ), ( 4, 6, 2, 5, 0.270, 2 ), # "OO", "oo" ( 1, 3, 0, 2, 0.280, 3 ), ( 4, 6, 0, 2, 0.280, 3 ), ( 1, 3, 3, 5, 0.280, 3 ), ( 4, 6, 3, 5, 0.280, 3 ), # "OOF, "of ( 1, 4, 1, 3, 0.290, 4 ), ( 4, 7, 1, 3, 0.290, 4 ), ] hcand_lists_exp[1] = [ # "BAR", "bar" ( 7, 10, 5, 8, 0.300, 0 ), # "AR", "ba" ( 8, 10, 5, 7, 0.310, 1 ), # "AR", "ar" ( 8, 10, 6, 8, 0.320, 2 ), ] hcand_lists_exp[2] = [ # "FOO", "foo" ( 10, 13, 8, 11, 0.250, 0 ), ( 10, 13, 11, 14, 0.250, 0 ), ( 10, 13, 16, 19, 0.250, 0 ), # "F", "foo" ( 10, 11, 8, 11, 0.260, 1 ), ( 10, 11, 11, 14, 0.260, 1 ), ( 10, 11, 16, 19, 0.260, 1 ), # "OO", "foo" ( 11, 13, 8, 11, 0.270, 2 ), ( 11, 13, 11, 14, 0.270, 2 ), ( 11, 13, 16, 19, 0.270, 2 ), ( 12, 14, 8, 11, 0.270, 2 ), ( 12, 14, 11, 14, 0.270, 2 ), ( 12, 14, 16, 19, 0.270, 2 ), # "OO", "oo" ( 11, 13, 9, 11, 0.280, 3 ), ( 11, 13, 12, 14, 0.280, 3 ), ( 11, 13, 13, 15, 0.280, 3 ), ( 11, 13, 14, 16, 0.280, 3 ), ( 11, 13, 17, 19, 0.280, 3 ), ( 12, 14, 9, 11, 0.280, 3 ), ( 12, 14, 12, 14, 0.280, 3 ), ( 12, 14, 13, 15, 0.280, 3 ), ( 12, 14, 14, 16, 0.280, 3 ), ( 12, 14, 17, 19, 0.280, 3 ), ] check_bitemplate_hit_candidate_lists(hcand_lists, hcand_lists_exp, text0, text1) return # ---------------------------------------------------------------------- def test_get_hit_candidate_lists_1(): err.write("\n\n\n") err.write(f"=== test_get_hit_candidates_0 ===========\n") text0 = """ 丹雄鸡味甘微温主女人崩中漏下赤白沃补虚温中止血通神杀毒辟不祥头主杀鬼东门上者尤良 肪主耳聋肠主遗溺肶胵裹黄皮主泄利屎白主消渴伤寒寒热翮羽主下血闭鸡子主除热火疮痫痉 可作虎魄神物鸡白蠹能肥脂生平泽 """ text0 = re.sub("[ \n]", "", text0) # 0 1 2 3 4 # 5 6 7 8 9 # 01234567890123456789012345678901234567890123456789 text1 = """ poarkeeodaiinqoairaracphheyqoeedeodyqokaiinqotedai raporairapylsheodytairoteeyoteeoolotaiinokeeyqokai inoraiiraldalsheeodaiinchsdqokeeeydairokaiinotaiin chedaiinolkallkldaindoeeokcheeoltaiinotcheedychora iinodaiinchedyotaiinalkaishdlaiinsheodokeeodyqoaii nytaiinotairchdaldydaimchdaiinockhhyysheyckhysheoq oeeolkaiinchsokoltchdysheeeyokaiinaraildycheodyoai irainokshey """ text1 = re.sub("[ \n]", "", text1) bipatA = ( ( 0.000, '主', "daiin" ), # 0 ( 0.002, '主', "dair" ), # 1 ( 0.024, '主', "dain" ), # 2 ( 0.026, '主', "daiiin" ), # 3 ( 0.060, '主', "kaiin" ), # 4 ( 0.070, '主', "laiin" ), # 5 ) bipatB = ( ( 0.000, '杀', "chsd" ), # 0 ( 0.001, '杀', "[ao]?keey" ), # 1 ( 0.002, '杀', "[ao]?keeey" ), # 2 ( 0.030, '杀', "[ao]?kaiin" ), # 3 ) bitemp = ( bipatA, bipatB, bipatA, bipatB, bipatA, bipatA, bipatA, bipatA, bipatA, bipatA, ) hcand_lists = get_hit_candidate_lists(bitemp, text0, text1) hcand_lists_exp = [ None, ]*10 hcand_lists_exp[0] = [ ( 7, 8, 8, 13, 0.000, 0, ), ( 7, 8, 118, 123, 0.000, 0, ), ( 7, 8, 47, 51, 0.002, 1, ), ( 7, 8, 38, 43, 0.060, 4, ), ( 7, 8, 97, 102, 0.060, 4, ), # ( 7, 8, 153, 158, 0.000, 0, ), # ( 7, 8, 204, 209, 0.000, 0, ), # ( 7, 8, 275, 280, 0.000, 0, ), # ( 7, 8, 134, 138, 0.002, 1, ), # ( 7, 8, 166, 170, 0.024, 2, ), # ( 7, 8, 139, 144, 0.060, 4, ), # ( 7, 8, 305, 310, 0.060, 4, ), # ( 7, 8, 329, 334, 0.060, 4, ), # ( 7, 8, 228, 233, 0.070, 5, ), ] hcand_lists_exp[1] = [ ( 25, 26, 123, 127, 0.000, 0 ), ( 25, 26, 90, 95, 0.001, 1 ), ( 25, 26, 91, 95, 0.001, 1 ), ( 25, 26, 128, 134, 0.002, 2 ), ( 25, 26, 129, 134, 0.002, 2 ), ( 25, 26, 37, 43, 0.030, 3 ), ( 25, 26, 38, 43, 0.030, 3 ), ( 25, 26, 96, 102, 0.030, 3 ), ( 25, 26, 97, 102, 0.030, 3 ), # ( 25, 26, 138, 144, 0.030, 3 ), # ( 25, 26, 139, 144, 0.030, 3 ), # ( 25, 26, 305, 310, 0.030, 3 ), # ( 25, 26, 328, 334, 0.030, 3 ), # ( 25, 26, 329, 334, 0.030, 3 ), ] hcand_lists_exp[2] = [ ( 31, 32, 47, 51, 0.002, 1, ), ( 31, 32, 97, 102, 0.060, 4, ), ( 31, 32, 118, 123, 0.000, 0, ), ( 31, 32, 134, 138, 0.002, 1, ), # ( 31, 32, 8, 13, 0.000, 0, ), # ( 31, 32, 38, 43, 0.060, 4, ), # ( 31, 32, 139, 144, 0.060, 4, ), # ( 31, 32, 153, 158, 0.000, 0, ), # ( 31, 32, 166, 170, 0.024, 2, ), # ( 31, 32, 204, 209, 0.000, 0, ), # ( 31, 32, 228, 233, 0.070, 5, ), # ( 31, 32, 275, 280, 0.000, 0, ), # ( 31, 32, 305, 310, 0.060, 4, ), # ( 31, 32, 329, 334, 0.060, 4, ), ] hcand_lists_exp[3] = [ ( 32, 33, 123, 127, 0.000, 0 ), ( 32, 33, 90, 95, 0.001, 1 ), ( 32, 33, 91, 95, 0.001, 1 ), ( 32, 33, 128, 134, 0.002, 2 ), ( 32, 33, 129, 134, 0.002, 2 ), ( 32, 33, 96, 102, 0.030, 3 ), ( 32, 33, 97, 102, 0.030, 3 ), ( 32, 33, 138, 144, 0.030, 3 ), ( 32, 33, 139, 144, 0.030, 3 ), # ( 32, 33, 37, 43, 0.030, 3 ), # ( 32, 33, 38, 43, 0.030, 3 ), # ( 32, 33, 305, 310, 0.030, 3 ), # ( 32, 33, 328, 334, 0.030, 3 ), # ( 32, 33, 329, 334, 0.030, 3 ), ] hcand_lists_exp[4] = [ ( 41, 42, 118, 123, 0.000, 0, ), ( 41, 42, 153, 158, 0.000, 0, ), ( 41, 42, 134, 138, 0.002, 1, ), ( 41, 42, 166, 170, 0.024, 2, ), ( 41, 42, 97, 102, 0.060, 4, ), ( 41, 42, 139, 144, 0.060, 4, ), # ( 41, 42, 329, 334, 0.060, 4, ), # ( 41, 42, 305, 310, 0.060, 4, ), # ( 41, 42, 275, 280, 0.000, 0, ), # ( 41, 42, 228, 233, 0.070, 5, ), # ( 41, 42, 204, 209, 0.000, 0, ), # ( 41, 42, 47, 51, 0.002, 1, ), # ( 41, 42, 38, 43, 0.060, 4, ), # ( 41, 42, 8, 13, 0.000, 0, ), ] hcand_lists_exp[5] = [ ( 45, 46, 118, 123, 0.000, 0, ), ( 45, 46, 153, 158, 0.000, 0, ), ( 45, 46, 204, 209, 0.000, 0, ), ( 45, 46, 134, 138, 0.002, 1, ), ( 45, 46, 166, 170, 0.024, 2, ), ( 45, 46, 139, 144, 0.060, 4, ), # ( 45, 46, 329, 334, 0.060, 4, ), # ( 45, 46, 305, 310, 0.060, 4, ), # ( 45, 46, 275, 280, 0.000, 0, ), # ( 45, 46, 228, 233, 0.070, 5, ), # ( 45, 46, 97, 102, 0.060, 4, ), # ( 45, 46, 47, 51, 0.002, 1, ), # ( 45, 46, 38, 43, 0.060, 4, ), # ( 45, 46, 8, 13, 0.000, 0, ), ] hcand_lists_exp[6] = [ ( 53, 54, 153, 158, 0.000, 0, ), ( 53, 54, 204, 209, 0.000, 0, ), ( 53, 54, 134, 138, 0.002, 1, ), ( 53, 54, 166, 170, 0.024, 2, ), ( 53, 54, 139, 144, 0.060, 4, ), ( 53, 54, 228, 233, 0.070, 5, ), # ( 53, 54, 329, 334, 0.060, 4, ), # ( 53, 54, 305, 310, 0.060, 4, ), # ( 53, 54, 275, 280, 0.000, 0, ), # ( 53, 54, 118, 123, 0.000, 0, ), # ( 53, 54, 97, 102, 0.060, 4, ), # ( 53, 54, 47, 51, 0.002, 1, ), # ( 53, 54, 38, 43, 0.060, 4, ), # ( 53, 54, 8, 13, 0.000, 0, ), ] hcand_lists_exp[7] = [ ( 58, 59, 153, 158, 0.000, 0, ), ( 58, 59, 204, 209, 0.000, 0, ), ( 58, 59, 275, 280, 0.000, 0, ), ( 58, 59, 166, 170, 0.024, 2, ), ( 58, 59, 139, 144, 0.060, 4, ), ( 58, 59, 228, 233, 0.070, 5, ), # ( 58, 59, 134, 138, 0.002, 1, ), # ( 58, 59, 329, 334, 0.060, 4, ), # ( 58, 59, 305, 310, 0.060, 4, ), # ( 58, 59, 118, 123, 0.000, 0, ), # ( 58, 59, 97, 102, 0.060, 4, ), # ( 58, 59, 47, 51, 0.002, 1, ), # ( 58, 59, 38, 43, 0.060, 4, ), # ( 58, 59, 8, 13, 0.000, 0, ), ] hcand_lists_exp[8] = [ ( 67, 68, 153, 158, 0.000, 0, ), ( 67, 68, 204, 209, 0.000, 0, ), ( 67, 68, 275, 280, 0.000, 0, ), ( 67, 68, 166, 170, 0.024, 2, ), ( 67, 68, 305, 310, 0.060, 4, ), ( 67, 68, 228, 233, 0.070, 5, ), # ( 67, 68, 329, 334, 0.060, 4, ), # ( 67, 68, 139, 144, 0.060, 4, ), # ( 67, 68, 134, 138, 0.002, 1, ), # ( 67, 68, 118, 123, 0.000, 0, ), # ( 67, 68, 97, 102, 0.060, 4, ), # ( 67, 68, 47, 51, 0.002, 1, ), # ( 67, 68, 38, 43, 0.060, 4, ), # ( 67, 68, 8, 13, 0.000, 0, ), ] hcand_lists_exp[9] = [ ( 73, 74, 204, 209, 0.000, 0, ), ( 73, 74, 275, 280, 0.000, 0, ), ( 73, 74, 166, 170, 0.024, 2, ), ( 73, 74, 305, 310, 0.060, 4, ), ( 73, 74, 329, 334, 0.060, 4, ), ( 73, 74, 228, 233, 0.070, 5, ), # ( 73, 74, 153, 158, 0.000, 0, ), # ( 73, 74, 139, 144, 0.060, 4, ), # ( 73, 74, 134, 138, 0.002, 1, ), # ( 73, 74, 118, 123, 0.000, 0, ), # ( 73, 74, 97, 102, 0.060, 4, ), # ( 73, 74, 47, 51, 0.002, 1, ), # ( 73, 74, 38, 43, 0.060, 4, ), # ( 73, 74, 8, 13, 0.000, 0, ), ] check_bitemplate_hit_candidate_lists(hcand_lists, hcand_lists_exp, text0, text1) return # ---------------------------------------------------------------------- if len(sys.argv) > 1 and sys.argv[1] == "BTF.TEST": test_get_hit_candidate_lists_0() test_get_hit_candidate_lists_1()