fenci.py

# -*- coding: UTF-8 -*-
import re
import sys

d = {}
def init(filename="SogouLabDic.dic"):
    f = open(filename, 'r')
    for line in f:
        word, freq = line.split('\t')[0:2]
        try:
            d[word.decode("gbk")] = int(freq)
        except:
            d[word] = int(freq)

def maxmatch(s):
    maxlen = 5
    l = len(s)
    p = 0
    result = {}
    while p < l:
        length = min(maxlen, l-p)
        wlen = 1
        for i in range(length, 0, -1):
            if d.has_key(s[p:p+i]):
                wlen = i
                break
        if wlen > 1:
            result.setdefault(s[p:p+wlen], 0)
            result[s[p:p+wlen]] += 1
        p += wlen

    return result

def maxmatch_back(s):
    maxlen = 5
    l = len(s)
    result = {}
    while l > 0:
        length = min(maxlen, l)
        wlen = 1
        for i in range(length, 0, -1):
            if d.has_key(s[l-i:l]):
                wlen = i
                break
        if wlen > 1:
            result.setdefault(s[l-wlen:l], 0)
            result[s[l-wlen:l]] += 1 
        l -= wlen

    return result
    
def one_word(s, start, rest=3):
    result = []
    maxlen = 5
    l = len(s)
    for former in start:
        p = former[len(former)-1]
        if p >= l: 
            result.append(former)
            break
        length = min(maxlen, l-p)
        num = 0
        for i in range(1, length+1):
            if d.has_key(s[p:p+i]):
                result.append(former + [p+i])
                num += 1
        if num == 0: result.append(former + [p+1])

    if rest > 1: return one_word(s, result, rest-1)
    else: return result
    
def three_word_chunk(s, start):
    result = one_word(s, [[start]], 3)
    longest = 0
    lset = []
    for i in range(len(result)):
        cur = result[i][len(result[i])-1] - result[i][0]
        if cur > longest:
            longest = cur
            lset = [i]
        elif cur == longest:
            lset.append(i)

    if len(lset) == 1:
        return result[lset[0]]
    else:
        # get the longest averge
        longavg = 0
        lavg = []
        for i in range(len(lset)):
            cur = longest / float(len(result[lset[i]])-1)
            if cur > longavg:
                longavg = cur
                lavg = [lset[i]]
            elif cur == longavg:
                lavg.append(lset[i])
        lset = lavg
        longest = longavg
        
    if len(lset) == 1:
        return result[lset[0]]
    else:
        # get the minmum dx
        mindk = sys.maxint
        dkset = []
        for i in range(len(lset)):
            cur = 0
            for j in range(1, len(result[lset[i]])):
                wordlen = result[lset[i]][j] - result[lset[i]][j-1]
                cur += pow((wordlen - longest), 2)
            
            if cur < mindk:
                mindk = cur
                dkset = [lset[i]]
            elif cur == mindk:
                dkset.append(lset[i])
        lset = dkset
        longest = mindk

    if len(lset) == 1:
        return result[lset[0]]
    else:
        # get the maxmum frequency
        maxFre = 0
        fset = []
        for i in range(len(lset)):
            cur = 0
            for j in range(1, len(result[i])):
                key = s[result[i][j-1]:result[i][j]]
                if d.has_key(key):
                    cur += d[key]
            if cur > maxFre:
                maxFre = cur
                fset = [lset[i]]
            elif cur == maxFre:
                fset.append(lset[i])
        lset = fset
        longest = maxFre

    if len(lset) == 1:
        return result[lset[0]]
    else:
#        print 'Really More than one...', lset
        return result[lset[0]]

# look ahead two more words
def mmseg(s):
    maxlen = 5
    l = len(s)
    p = 0

    result = {}
    while p < l:
        chunk = three_word_chunk(s, p)
        if(len(chunk) < 2): break

        if chunk[1] - chunk[0] > 1:
            result.setdefault(s[chunk[0]:chunk[1]], 0)
            result[s[chunk[0]:chunk[1]]] += 1
        p = chunk[1]
    return result

def solve(s, segment=maxmatch):
    s = s.decode("utf8")
    return segment(s)