#! /usr/bin/python3 # Last edited on 2026-07-05 03:43:54 by stolfi import os,sys,re from process_funcs import basic_line_loop from sys import stdin as inp, stdout as out, stderr as err def main(text_name): # Reads "res/{text_name}.txt" with tokens separated by blanks, # possibly with a locus ID "<...>" at the beginning of each line. # # Writes three files: # # "res/{text_name}.rct" number of {k}-repeats for each {k}. # "res/{text_name}.stp" stop pairs that ended the repeats. # "res/{text_name}.rex" list of all repeats of 4 or more tokens. # # let {tokens[0..nt-1]} be the tokens in the input file. # A /{k}-repeat exists/ at any two token indices {i0,i1} such that # # (0) {0 <= i0 < i1 < nt} # (1) {tokens[i0+r]} and {tokens[i1+r]} are similar for all {r} in {0..k-1}, # (2) {tokens[i0-1]} and {tokens[i1-1]} are not similar, # (3) {tokens[i0+k]} and {tokens[i1+k]} are not similar, and # # The pairs mentioned in (2) and (3) are the /stop pairs/ of the repeat. # A {k} repeat at {i0,i1} is said to be /proper/ if # # (4) There exist no {k} repeat {i0,im} with {i0 < im < i1}. # # A /{k}-repeat group/ is a maximal set of two or more indices such that # for any distinct {i0,i1} in it there exists a {k}-repeat between them. # # This script ignores 1-repeats since those can be calculated from the # word count file. # # The ".rex" file has one line for each phrase (string of tokens) that is a # member of a {k}-repeat for any {k} that is 2 or more. The line has # the following fields: # # {ITHIS} index (from 0) of the first token of the phrase. # {LINUM} line number (from 1) where that token was read from. # {IPREV} index of first token of the previous occurence, or {-1}. # {INEXT} index of first token of the next occurrence, or {999999}. # {K} number of words in the phrase. # {TOKS}.. the tokens of the phrase. # # The fields {IPREV} and {INEXT} link together all members of # the same {k}-repeat group. # # The count of {k}-repeats is the count of index pairs that # consitute proper {k}-repeats. Thus each {k}-repeat group # with {m} members contributes {m-1} to this count. err.write(f"looking for repeated phrases ...\n") tokens = [] # The stream of tokens, ignoring line boundaries. linums = [] # The line numbers where each token was found. def process_line(nread, line): line = re.sub(r"<[^<>]*>", " ", line) for tok in line.split(): tokens.append(tok) linums.append(nread) return # :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: text_file = f"res/{text_name}.txt" rd = open(text_file, "r") nread = basic_line_loop(rd, process_line) rd.close() nt = len(tokens) err.write(f"read {nread} lines, got {nt} tokens.\n") # Output file with repetition counts: rep_rct_file = f"res/{text_name}.rct" wr_rct = open(rep_rct_file, "w") # Output file with stop pairs: rep_stp_file = f"res/{text_name}.stp" wr_stp = open(rep_stp_file, "w") wr_stp.reconfigure(encoding='utf-8') wr_stp.write("# -*- coding: utf-8 -*-\n") # Output file with repetition sequences: rep_rex_file = f"res/{text_name}.rex" wr_rex = open(rep_rex_file, "w") wr_rex.reconfigure(encoding='utf-8') wr_rex.write("# -*- coding: utf-8 -*-\n") def one_insertion(wda, wdb): # True iff {wda} is {wdb} with exactly one extra letter. nca = len(wda); assert nca == len(wdb) + 1 for ica in range(nca): wds = wda[:ica] + wda[ica+1:] if wds == wdb: return True return False # :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: def repeat_length(i0,i1): # Returns the max number {k} such that {tokens[i0+r] ~ tokens[i1+r]} # for {r} in {0..k-1}, with {tokens[i0+k] !~ tokens[i1+k]} and # {tokens[i0-1] ~ tokens[i1-1]}. # # If there is no such {k}, returns None assert 0 <= i0 and i0 < i1 and i1 < nt if not tokens[i0] == tokens[i1]: return None if i0 >= 1 and tokens[i0-1] == tokens[i1-1]: return None k = 1 while i1+k < nt and tokens[i0+k] == tokens[i1+k]: k += 1 return k # :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: def output_repeat(ith, ipr, inx, k): # Writes a repeating sequence to {wr_rex}. # assert 0 <= ith and ith < nt wr_rex.write(f"{ith:6d}") nl = linums[ith] wr_rex.write(f" {nl:5d}") wr_rex.write(f" {ipr:6d}") if inx >= nt: inx = 999999 wr_rex.write(f" {inx:6d}") wr_rex.write(f" {k:3d}") for r in range(k): wr_rex.write(" "); wr_rex.write(tokens[ith+r]) wr_rex.write("\n") return # :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: def show_stops(ia, ib, k): # Shows the two words that prevented a {k}-repeat from growing into a # longer repeat, both at the low and the high end. Namely. # {tokens[ia-1],tokens[ib-1]} and {tokens[ia+k],tokens[ib+k]}, # if they exist. # # The words in each pair are sorted alphabetically. # assert 0 <= ia and ia < ib and ib+k <= nt for d in -1, k: if ia+d >= 0 and ib+d < nt: wa = tokens[ia+d] wb = tokens[ib+d] if wa > wb: wb,wa = wa,wb wr_stp.write(f"{wa} {wb}\n") return # :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: # Now find the repeats: # Don't bother with 1-repeats. kmax = 0 # Max length of a repeat found. kmin_out = 2 # Min {k} to write output. kmin_tct = 5 # Min {k} to count in total. prev_rep = [ None ] * nt next_rep = [ None ] * nt # We set {prev_rep[i1][k]} to the max {i0} s.t. {i0,i1} a {k}-repeat # candidate, or {-1}. We also set {next_rep[i0][k]} to the min {i1} # s.t. {i0,i1} a {k}-repeat candidate, or {nt}. However {prev_rep[i1]} # and {next_rep[i0]} are {None} if there are no repeats other than # trivial ({k==1}) at those places. for i0 in range(nt): for i1 in range(i0+1, nt): if tokens[i0] == tokens[i1]: k = repeat_length(i0, i1) if k != None: if k > kmax: kmax = k if k >= 2: # Set {next_rep[i0][k]} to index of earliest repeat: # Allocate {next_rep,prev_rep} as needed: if next_rep[i0] == None: next_rep[i0] = [ nt, nt, ] nx0 = next_rep[i0]; while len(nx0) <= k: nx0.append(nt) if nx0[k] == nt: nx0[k] = i1 # Set {prev_rep[i1][k]} to index of latest repeat: if prev_rep[i1] == None: prev_rep[i1] = [ -1, -1, ] pr1 = prev_rep[i1] while len(pr1) <= k: pr1.append(-1) pr1[k] = i0 err.write(f"max length of repeat = {kmax}\n") # Now scan {prev_rep,next_rep} to get the proper {k}-repeats. nreps = [ 0 ] * (kmax+1) # {nreps[k]} is the number of {k}-repeats found. for ith in range(nt): prt = prev_rep[ith]; prev_kmax = 0 if prt == None else len(prt)-1 nxt = next_rep[ith]; next_kmax = 0 if nxt == None else len(nxt)-1 for k in range(2, max(prev_kmax,next_kmax)+1): ipr = -1 if prt == None or k > prev_kmax else prt[k] inx = nt if nxt == None or k > next_kmax else nxt[k] if ipr >= 0 or inx < nt: # There is at least one {k}-repeat with {ith} as one of the indices: assert ith + k <= nt if k >= kmin_out: output_repeat(ith, ipr, inx, k) if ipr != -1: # Got a proper {k}-repeat at {ipr,ith} nreps[k] += 1; show_stops(ipr, ith, k) assert len(nreps) == kmax+1 treps = 0 for k in range(2,kmax+1): wr_rct.write(f"{k:3d} {nreps[k]}\n") if nreps[k] > 0: err.write(f"found {nreps[k]} {k}-repeats\n") if k >= kmin_tct: treps += nreps[k] err.write(f"found {treps} k-repeats with k >= {kmin_tct}\n") wr_rct.close() wr_rex.close() wr_stp.close() return # ---------------------------------------------------------------------- text_name = sys.argv[1] main(text_name)