natural language toolkit texttiling c 20012023 nltk project george boutsioukis url https www nltk org for license information see license txt tokenize a document into topical sections using the texttiling algorithm this algorithm detects subtopic shifts based on the analysis of lexical cooccurrence patterns the process starts by tokenizing the text into pseudosentences of a fixed size w then depending on the method used similarity scores are assigned at sentence gaps the algorithm proceeds by detecting the peak differences between these scores and marking them as boundaries the boundaries are normalized to the closest paragraph break and the segmented text is returned param w pseudosentence size type w int param k size in sentences of the block used in the block comparison method type k int param similaritymethod the method used for determining similarity scores blockcomparison default or vocabularyintroduction type similaritymethod constant param stopwords a list of stopwords that are filtered out defaults to nltk s stopwords corpus type stopwords liststr param smoothingmethod the method used for smoothing the score plot defaultsmoothing default type smoothingmethod constant param smoothingwidth the width of the window used by the smoothing method type smoothingwidth int param smoothingrounds the number of smoothing passes type smoothingrounds int param cutoffpolicy the policy used to determine the number of boundaries hc default or lc type cutoffpolicy constant from nltk corpus import brown tt texttilingtokenizerdemomodetrue text brown raw 4000 s ss d b tt tokenizetext b 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 return a tokenized copy of text where each token represents a separate topic lowercasetext text lower paragraphbreaks self markparagraphbreakstext textlength lenlowercasetext tokenization step starts here remove punctuation nopuncttext join c for c in lowercasetext if re matchraz nt c nopunctparbreaks self markparagraphbreaksnopuncttext tokseqs self dividetotokensequencesnopuncttext the morphological stemming step mentioned in the texttile paper is not implemented a comment in the original c implementation states that it offers no benefit to the process it might be interesting to test the existing stemmers though words stemwordswords filter stopwords for ts in tokseqs ts wrdindexlist wi for wi in ts wrdindexlist if wi0 not in self stopwords tokentable self createtokentabletokseqs nopunctparbreaks end of the tokenization step lexical score determination if self similaritymethod blockcomparison gapscores self blockcomparisontokseqs tokentable elif self similaritymethod vocabularyintroduction raise notimplementederrorvocabulary introduction not implemented else raise valueerror fsimilarity method self similaritymethod not recognized if self smoothingmethod defaultsmoothing smoothscores self smoothscoresgapscores else raise valueerrorfsmoothing method self smoothingmethod not recognized end of lexical score determination boundary identification depthscores self depthscoressmoothscores segmentboundaries self identifyboundariesdepthscores normalizedboundaries self normalizeboundaries text segmentboundaries paragraphbreaks end of boundary identification segmentedtext prevb 0 for b in normalizedboundaries if b 0 continue segmentedtext appendtextprevb b prevb b if prevb textlength append any text that may be remaining segmentedtext appendtextprevb if not segmentedtext segmentedtext text if self demomode return gapscores smoothscores depthscores segmentboundaries return segmentedtext def blockcomparisonself tokseqs tokentable adjust window size for boundary conditions identifies indented text or line breaks as the beginning of paragraphs minparagraph 100 pattern re compile trfvn trfvn trfv matches pattern finditertext lastbreak 0 pbreaks 0 for pb in matches if pb start lastbreak minparagraph continue else pbreaks appendpb start lastbreak pb start return pbreaks def dividetotokensequencesself text divides the text into pseudosentences of fixed size w self w wrdindexlist matches re finditerrw text for match in matches wrdindexlist appendmatch group match start return tokensequencei w wrdindexlisti i w for i in range0 lenwrdindexlist w def createtokentableself tokensequences parbreaks creates a table of tokentablefields tokentable currentpar 0 currenttokseq 0 pbiter parbreaks iter currentparbreak nextpbiter if currentparbreak 0 try currentparbreak nextpbiter skip break at 0 except stopiteration as e raise valueerror no paragraph breaks were foundtext too short perhaps from e for ts in tokensequences for word index in ts wrdindexlist try while index currentparbreak currentparbreak nextpbiter currentpar 1 except stopiteration hit bottom pass if word in tokentable tokentableword totalcount 1 if tokentableword lastpar currentpar tokentableword lastpar currentpar tokentableword parcount 1 if tokentableword lasttokseq currenttokseq tokentableword lasttokseq currenttokseq tokentableword tsoccurences appendcurrenttokseq 1 else tokentableword tsoccurences11 1 else new word tokentableword tokentablefield firstposindex tsoccurencescurrenttokseq 1 totalcount1 parcount1 lastparcurrentpar lasttokseqcurrenttokseq currenttokseq 1 return tokentable def identifyboundariesself depthscores calculates the depth of each gap i e the average difference between the left and right peaks and the gap s score depthscores 0 for x in scores clip boundaries this holds on the rule of thumbmy thumb that a section shouldn t be smaller than at least 2 pseudosentences for small texts and around 5 for larger ones clip minmaxlenscores 10 2 5 index clip for gapscore in scoresclip clip lpeak gapscore for score in scoresindex 1 if score lpeak lpeak score else break rpeak gapscore for score in scoresindex if score rpeak rpeak score else break depthscoresindex lpeak rpeak 2 gapscore index 1 return depthscores def normalizeboundariesself text boundaries paragraphbreaks find closest paragraph break a field in the token table holding parameters for each token used later in the process def init self firstpos tsoccurences totalcount1 parcount1 lastpar0 lasttokseqnone self dict updatelocals del self dictself class tokensequence a token list with its original length and its index def initself index wrdindexlist originallengthnone originallength originallength or lenwrdindexlist self dict updatelocals del self dictself pasted from the scipy cookbook https www scipy orgcookbooksignalsmooth def smoothx windowlen11 windowflat if x ndim 1 raise valueerrorsmooth only accepts 1 dimension arrays if x size windowlen raise valueerrorinput vector needs to be bigger than window size if windowlen 3 return x if window not in flat hanning hamming bartlett blackman raise valueerror window is on of flat hanning hamming bartlett blackman s numpy r2 x0 xwindowlen 1 1 x 2 x1 x1 windowlen 1 printlens if window flat moving average w numpy oneswindowlen d else w evalnumpy window windowlen y numpy convolvew w sum s modesame return ywindowlen 1 windowlen 1 def demotextnone from matplotlib import pylab from nltk corpus import brown tt texttilingtokenizerdemomodetrue if text is none text brown raw 10000 s ss d b tt tokenizetext pylab xlabelsentence gap index pylab ylabelgap scores pylab plotrangelens s labelgap scores pylab plotrangelenss ss labelsmoothed gap scores pylab plotrangelend d labeldepth scores pylab stemrangelenb b pylab legend pylab show natural language toolkit texttiling c 2001 2023 nltk project george boutsioukis url https www nltk org for license information see license txt tokenize a document into topical sections using the texttiling algorithm this algorithm detects subtopic shifts based on the analysis of lexical co occurrence patterns the process starts by tokenizing the text into pseudosentences of a fixed size w then depending on the method used similarity scores are assigned at sentence gaps the algorithm proceeds by detecting the peak differences between these scores and marking them as boundaries the boundaries are normalized to the closest paragraph break and the segmented text is returned param w pseudosentence size type w int param k size in sentences of the block used in the block comparison method type k int param similarity_method the method used for determining similarity scores block_comparison default or vocabulary_introduction type similarity_method constant param stopwords a list of stopwords that are filtered out defaults to nltk s stopwords corpus type stopwords list str param smoothing_method the method used for smoothing the score plot default_smoothing default type smoothing_method constant param smoothing_width the width of the window used by the smoothing method type smoothing_width int param smoothing_rounds the number of smoothing passes type smoothing_rounds int param cutoff_policy the policy used to determine the number of boundaries hc default or lc type cutoff_policy constant from nltk corpus import brown tt texttilingtokenizer demo_mode true text brown raw 4000 s ss d b tt tokenize text b 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 return a tokenized copy of text where each token represents a separate topic tokenization step starts here remove punctuation the morphological stemming step mentioned in the texttile paper is not implemented a comment in the original c implementation states that it offers no benefit to the process it might be interesting to test the existing stemmers though words _stem_words words filter stopwords end of the tokenization step lexical score determination end of lexical score determination boundary identification end of boundary identification append any text that may be remaining implements the block comparison method adjust window size for boundary conditions score 0 0 identifies indented text or line breaks as the beginning of paragraphs skip break at 0 hit bottom new word identifies boundaries at the peaks of similarity score differences undo if there is a boundary close already calculates the depth of each gap i e the average difference between the left and right peaks and the gap s score clip boundaries this holds on the rule of thumb my thumb that a section shouldn t be smaller than at least 2 pseudosentences for small texts and around 5 for larger ones normalize the boundaries identified to the original text s paragraph breaks find closest paragraph break avoid duplicates a field in the token table holding parameters for each token used later in the process pasted from the scipy cookbook https www scipy org cookbook signalsmooth smooth the data using a window with requested size this method is based on the convolution of a scaled window with the signal the signal is prepared by introducing reflected copies of the signal with the window size in both ends so that transient parts are minimized in the beginning and end part of the output signal param x the input signal param window_len the dimension of the smoothing window should be an odd integer param window the type of window from flat hanning hamming bartlett blackman flat window will produce a moving average smoothing return the smoothed signal example t linspace 2 2 0 1 x sin t randn len t 0 1 y smooth x see also numpy hanning numpy hamming numpy bartlett numpy blackman numpy convolve scipy signal lfilter todo the window parameter could be the window itself if an array instead of a string print len s moving average
import math
import re

try:
    import numpy
except ImportError:
    pass

from nltk.tokenize.api import TokenizerI

BLOCK_COMPARISON, VOCABULARY_INTRODUCTION = 0, 1
LC, HC = 0, 1
DEFAULT_SMOOTHING = [0]


class TextTilingTokenizer(TokenizerI):
    

    def __init__(
        self,
        w=20,
        k=10,
        similarity_method=BLOCK_COMPARISON,
        stopwords=None,
        smoothing_method=DEFAULT_SMOOTHING,
        smoothing_width=2,
        smoothing_rounds=1,
        cutoff_policy=HC,
        demo_mode=False,
    ):

        if stopwords is None:
            from nltk.corpus import stopwords

            stopwords = stopwords.words("english")
        self.__dict__.update(locals())
        del self.__dict__["self"]

    def tokenize(self, text):
        

        lowercase_text = text.lower()
        paragraph_breaks = self._mark_paragraph_breaks(text)
        text_length = len(lowercase_text)

        

        
        nopunct_text = "".join(
            c for c in lowercase_text if re.match(r"[a-z\-' \n\t]", c)
        )
        nopunct_par_breaks = self._mark_paragraph_breaks(nopunct_text)

        tokseqs = self._divide_to_tokensequences(nopunct_text)

        
        
        
        
        
        

        
        for ts in tokseqs:
            ts.wrdindex_list = [
                wi for wi in ts.wrdindex_list if wi[0] not in self.stopwords
            ]

        token_table = self._create_token_table(tokseqs, nopunct_par_breaks)
        

        
        if self.similarity_method == BLOCK_COMPARISON:
            gap_scores = self._block_comparison(tokseqs, token_table)
        elif self.similarity_method == VOCABULARY_INTRODUCTION:
            raise NotImplementedError("Vocabulary introduction not implemented")
        else:
            raise ValueError(
                f"Similarity method {self.similarity_method} not recognized"
            )

        if self.smoothing_method == DEFAULT_SMOOTHING:
            smooth_scores = self._smooth_scores(gap_scores)
        else:
            raise ValueError(f"Smoothing method {self.smoothing_method} not recognized")
        

        
        depth_scores = self._depth_scores(smooth_scores)
        segment_boundaries = self._identify_boundaries(depth_scores)

        normalized_boundaries = self._normalize_boundaries(
            text, segment_boundaries, paragraph_breaks
        )
        
        segmented_text = []
        prevb = 0

        for b in normalized_boundaries:
            if b == 0:
                continue
            segmented_text.append(text[prevb:b])
            prevb = b

        if prevb < text_length:  
            segmented_text.append(text[prevb:])

        if not segmented_text:
            segmented_text = [text]

        if self.demo_mode:
            return gap_scores, smooth_scores, depth_scores, segment_boundaries
        return segmented_text

    def _block_comparison(self, tokseqs, token_table):
        

        def blk_frq(tok, block):
            ts_occs = filter(lambda o: o[0] in block, token_table[tok].ts_occurences)
            freq = sum(tsocc[1] for tsocc in ts_occs)
            return freq

        gap_scores = []
        numgaps = len(tokseqs) - 1

        for curr_gap in range(numgaps):
            score_dividend, score_divisor_b1, score_divisor_b2 = 0.0, 0.0, 0.0
            score = 0.0
            
            if curr_gap < self.k - 1:
                window_size = curr_gap + 1
            elif curr_gap > numgaps - self.k:
                window_size = numgaps - curr_gap
            else:
                window_size = self.k

            b1 = [ts.index for ts in tokseqs[curr_gap - window_size + 1 : curr_gap + 1]]
            b2 = [ts.index for ts in tokseqs[curr_gap + 1 : curr_gap + window_size + 1]]

            for t in token_table:
                score_dividend += blk_frq(t, b1) * blk_frq(t, b2)
                score_divisor_b1 += blk_frq(t, b1) ** 2
                score_divisor_b2 += blk_frq(t, b2) ** 2
            try:
                score = score_dividend / math.sqrt(score_divisor_b1 * score_divisor_b2)
            except ZeroDivisionError:
                pass  

            gap_scores.append(score)

        return gap_scores

    def _smooth_scores(self, gap_scores):
        "Wraps the smooth function from the SciPy Cookbook"
        return list(
            smooth(numpy.array(gap_scores[:]), window_len=self.smoothing_width + 1)
        )

    def _mark_paragraph_breaks(self, text):
        
        MIN_PARAGRAPH = 100
        pattern = re.compile("[ \t\r\f\v]*\n[ \t\r\f\v]*\n[ \t\r\f\v]*")
        matches = pattern.finditer(text)

        last_break = 0
        pbreaks = [0]
        for pb in matches:
            if pb.start() - last_break < MIN_PARAGRAPH:
                continue
            else:
                pbreaks.append(pb.start())
                last_break = pb.start()

        return pbreaks

    def _divide_to_tokensequences(self, text):
        "Divides the text into pseudosentences of fixed size"
        w = self.w
        wrdindex_list = []
        matches = re.finditer(r"\w+", text)
        for match in matches:
            wrdindex_list.append((match.group(), match.start()))
        return [
            TokenSequence(i / w, wrdindex_list[i : i + w])
            for i in range(0, len(wrdindex_list), w)
        ]

    def _create_token_table(self, token_sequences, par_breaks):
        "Creates a table of TokenTableFields"
        token_table = {}
        current_par = 0
        current_tok_seq = 0
        pb_iter = par_breaks.__iter__()
        current_par_break = next(pb_iter)
        if current_par_break == 0:
            try:
                current_par_break = next(pb_iter)  
            except StopIteration as e:
                raise ValueError(
                    "No paragraph breaks were found(text too short perhaps?)"
                ) from e
        for ts in token_sequences:
            for word, index in ts.wrdindex_list:
                try:
                    while index > current_par_break:
                        current_par_break = next(pb_iter)
                        current_par += 1
                except StopIteration:
                    
                    pass

                if word in token_table:
                    token_table[word].total_count += 1

                    if token_table[word].last_par != current_par:
                        token_table[word].last_par = current_par
                        token_table[word].par_count += 1

                    if token_table[word].last_tok_seq != current_tok_seq:
                        token_table[word].last_tok_seq = current_tok_seq
                        token_table[word].ts_occurences.append([current_tok_seq, 1])
                    else:
                        token_table[word].ts_occurences[-1][1] += 1
                else:  
                    token_table[word] = TokenTableField(
                        first_pos=index,
                        ts_occurences=[[current_tok_seq, 1]],
                        total_count=1,
                        par_count=1,
                        last_par=current_par,
                        last_tok_seq=current_tok_seq,
                    )

            current_tok_seq += 1

        return token_table

    def _identify_boundaries(self, depth_scores):
        

        boundaries = [0 for x in depth_scores]

        avg = sum(depth_scores) / len(depth_scores)
        stdev = numpy.std(depth_scores)

        if self.cutoff_policy == LC:
            cutoff = avg - stdev
        else:
            cutoff = avg - stdev / 2.0

        depth_tuples = sorted(zip(depth_scores, range(len(depth_scores))))
        depth_tuples.reverse()
        hp = list(filter(lambda x: x[0] > cutoff, depth_tuples))

        for dt in hp:
            boundaries[dt[1]] = 1
            for dt2 in hp:  
                if (
                    dt[1] != dt2[1]
                    and abs(dt2[1] - dt[1]) < 4
                    and boundaries[dt2[1]] == 1
                ):
                    boundaries[dt[1]] = 0
        return boundaries

    def _depth_scores(self, scores):
        

        depth_scores = [0 for x in scores]
        
        
        

        clip = min(max(len(scores) // 10, 2), 5)
        index = clip

        for gapscore in scores[clip:-clip]:
            lpeak = gapscore
            for score in scores[index::-1]:
                if score >= lpeak:
                    lpeak = score
                else:
                    break
            rpeak = gapscore
            for score in scores[index:]:
                if score >= rpeak:
                    rpeak = score
                else:
                    break
            depth_scores[index] = lpeak + rpeak - 2 * gapscore
            index += 1

        return depth_scores

    def _normalize_boundaries(self, text, boundaries, paragraph_breaks):
        

        norm_boundaries = []
        char_count, word_count, gaps_seen = 0, 0, 0
        seen_word = False

        for char in text:
            char_count += 1
            if char in " \t\n" and seen_word:
                seen_word = False
                word_count += 1
            if char not in " \t\n" and not seen_word:
                seen_word = True
            if gaps_seen < len(boundaries) and word_count > (
                max(gaps_seen * self.w, self.w)
            ):
                if boundaries[gaps_seen] == 1:
                    
                    best_fit = len(text)
                    for br in paragraph_breaks:
                        if best_fit > abs(br - char_count):
                            best_fit = abs(br - char_count)
                            bestbr = br
                        else:
                            break
                    if bestbr not in norm_boundaries:  
                        norm_boundaries.append(bestbr)
                gaps_seen += 1

        return norm_boundaries


class TokenTableField:
    

    def __init__(
        self,
        first_pos,
        ts_occurences,
        total_count=1,
        par_count=1,
        last_par=0,
        last_tok_seq=None,
    ):
        self.__dict__.update(locals())
        del self.__dict__["self"]


class TokenSequence:
    "A token list with its original length and its index"

    def __init__(self, index, wrdindex_list, original_length=None):
        original_length = original_length or len(wrdindex_list)
        self.__dict__.update(locals())
        del self.__dict__["self"]



def smooth(x, window_len=11, window="flat"):
    

    if x.ndim != 1:
        raise ValueError("smooth only accepts 1 dimension arrays.")

    if x.size < window_len:
        raise ValueError("Input vector needs to be bigger than window size.")

    if window_len < 3:
        return x

    if window not in ["flat", "hanning", "hamming", "bartlett", "blackman"]:
        raise ValueError(
            "Window is on of 'flat', 'hanning', 'hamming', 'bartlett', 'blackman'"
        )

    s = numpy.r_[2 * x[0] - x[window_len:1:-1], x, 2 * x[-1] - x[-1:-window_len:-1]]

    
    if window == "flat":  
        w = numpy.ones(window_len, "d")
    else:
        w = eval("numpy." + window + "(window_len)")

    y = numpy.convolve(w / w.sum(), s, mode="same")

    return y[window_len - 1 : -window_len + 1]


def demo(text=None):
    from matplotlib import pylab

    from nltk.corpus import brown

    tt = TextTilingTokenizer(demo_mode=True)
    if text is None:
        text = brown.raw()[:10000]
    s, ss, d, b = tt.tokenize(text)
    pylab.xlabel("Sentence Gap index")
    pylab.ylabel("Gap Scores")
    pylab.plot(range(len(s)), s, label="Gap Scores")
    pylab.plot(range(len(ss)), ss, label="Smoothed Gap scores")
    pylab.plot(range(len(d)), d, label="Depth scores")
    pylab.stem(range(len(b)), b)
    pylab.legend()
    pylab.show()