src/lexicon/pytrie.cpp

/*
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
 *
 * Copyright (c) 2007 Sun Microsystems, Inc. All Rights Reserved.
 *
 * The contents of this file are subject to the terms of either the GNU Lesser
 * General Public License Version 2.1 only ("LGPL") or the Common Development and
 * Distribution License ("CDDL")(collectively, the "License"). You may not use this
 * file except in compliance with the License. You can obtain a copy of the CDDL at
 * http://www.opensource.org/licenses/cddl1.php and a copy of the LGPLv2.1 at
 * http://www.opensource.org/licenses/lgpl-license.php. See the License for the
 * specific language governing permissions and limitations under the License. When
 * distributing the software, include this License Header Notice in each file and
 * include the full text of the License in the License file as well as the
 * following notice:
 *
 * NOTICE PURSUANT TO SECTION 9 OF THE COMMON DEVELOPMENT AND DISTRIBUTION LICENSE
 * (CDDL)
 * For Covered Software in this distribution, this License shall be governed by the
 * laws of the State of California (excluding conflict-of-law provisions).
 * Any litigation relating to this License shall be subject to the jurisdiction of
 * the Federal Courts of the Northern District of California and the state courts
 * of the State of California, with venue lying in Santa Clara County, California.
 *
 * Contributor(s):
 *
 * If you wish your version of this file to be governed by only the CDDL or only
 * the LGPL Version 2.1, indicate your decision by adding "[Contributor]" elects to
 * include this software in this distribution under the [CDDL or LGPL Version 2.1]
 * license." If you don't indicate a single choice of license, a recipient has the
 * option to distribute your version of this file under either the CDDL or the LGPL
 * Version 2.1, or to extend the choice of license to its licensees as provided
 * above. However, if you add LGPL Version 2.1 code and therefore, elected the LGPL
 * Version 2 license, then the option applies only if the new code is made subject
 * to such option by the copyright holder.
 */

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <stdio.h>
#include <fcntl.h>
#include <unistd.h>
#include <deque>

#ifdef HAVE_SYS_MMAN_H
#include <sys/mman.h>
#endif

#include "pytrie.h"

const unsigned char CPinyinTrie::SYLLABLE_BREAKER;

const CPinyinTrie::TNode*
CPinyinTrie::transfer(const TNode* pnode, const unsigned char* str) const
{
    if (str) {
        for (; *str != 0 && pnode != NULL; ++str)
            pnode = transfer(pnode, *str);
    }
    return pnode;
}

const CPinyinTrie::TNode*
CPinyinTrie::transfer(const TNode* pnode, const TWCHAR* wstr) const
{
    if (wstr) {
        for (; *wstr != WCH_NULL && pnode != NULL; ++wstr)
            pnode = transfer(pnode, unsigned(*wstr));
    }
    return pnode;
}

const CPinyinTrie::TNode*
CPinyinTrie::transfer(const TNode* pnode, const unsigned char* str, int nlen) const
{
    if (str && nlen > 0) {
        for (; nlen>0 && *str != 0 && pnode != NULL; --nlen)
            pnode = transfer(pnode, *str++);
    }
    return pnode;
}

const CPinyinTrie::TNode*
CPinyinTrie::transfer(const TNode* pnode, const TWCHAR* wstr, int nlen) const
{
    if (wstr && nlen > 0) {
        for (; nlen>0 && *wstr != WCH_NULL && pnode != NULL; --nlen)
            pnode = transfer(pnode, unsigned(*wstr++));
    }
    return pnode;
}

bool
CPinyinTrie::isValid(const TNode* pnode, bool allowNonComplete, bool allowGBK)
{
    if ((pnode != NULL) && (allowGBK || pnode->m_bGBK == 0) && (pnode->transfer(SYLLABLE_BREAKER) != 0))
        return (allowNonComplete || (pnode->m_bFullSyllableTransfer == 1));
    return false;
}

unsigned int
CPinyinTrie::TNode::transfer(unsigned char c) const
{
    unsigned int s = 0, t = m_nTransfer;
    const TTransUnit* ptrans = getTrans();
    while (s < t) {
        int m = (s+t)/2;
        if (ptrans[m].m_Char == c)
            return ptrans[m].m_Offset;
        if (ptrans[m].m_Char < c)
            s = m + 1;
        else
            t = m;
    }
    return 0;
}

int
CPinyinTrie::lengthAt(unsigned int idx) const
{
    if (idx < getWordCount() -1 ) {
       return (m_words[idx+1] - m_words[idx]) - 1;
    } else if (idx == getWordCount() - 1) {
        return (((TWCHAR*)(m_mem+m_Size))-m_words[idx])-1;
    }
    return 0;
}

void
CPinyinTrie::print(FILE *fp) const
{
    std::string prefix;
    print(getRootNode(), prefix, fp);
}

void
CPinyinTrie::print(const TNode* pRoot, std::string& prefix, FILE *fp) const
{
    static char buf[1024];
    if (pRoot->m_nWordId > 0) {
        fprintf(fp, "%s", prefix.c_str());
        if (pRoot->m_bGBK)
            fprintf(fp, "(PureGBK)");
        unsigned int sz = pRoot->m_nWordId;
        const TWordIdInfo *pwids = pRoot->getWordIdPtr();
        for (unsigned int i = 0; i < sz; ++i) {
            unsigned int id = pwids[i].m_id;
            const TWCHAR *pw = operator[](id);
            int len = WCSLEN(pw);
            if (len != lengthAt(id)) {
                printf(" (lengthAt %d error) ", id);
            }
            WCSTOMBS(buf, pw, 1024);
            fprintf(fp, " %s", buf);
            if (pwids[i].m_bSeen == 0)
                fprintf(fp, "[x]");
            else
                fprintf(fp, "[o]");
        }
        fprintf(fp, "\n");
    }
    unsigned int sz = pRoot->m_nTransfer;
    const TTransUnit* ptrans = pRoot->getTrans();
    for (unsigned int i = 0; i < sz; ++i) {
        unsigned char c = (unsigned char)(ptrans[i].m_Char);
        const TNode *pch = transfer(pRoot, c);
        prefix += c;
        print(pch, prefix, fp);
        prefix.resize(prefix.size()-1);
    }
}

unsigned int
CPinyinTrie::getSimbolId(const TWCHAR* wstr)
{
    std::map<wstring, unsigned>::const_iterator it;

    it = m_SimbolMap.find(wstring(wstr));
    if (it != m_SimbolMap.end())
        return it->second;
    return 0;
}

unsigned int
CPinyinTrie::getSimbolId(const wstring & wstr)
{
    std::map<wstring, unsigned>::const_iterator it;

    it = m_SimbolMap.find(wstr);
    if (it != m_SimbolMap.end())
        return it->second;
    return 0;
}

void
CPinyinTrie::free(void)
{
    if (m_mem) {
#ifdef HAVE_SYS_MMAN_H
        m_mem -= sizeof(unsigned int);
        m_Size += sizeof(unsigned int);
        munmap (m_mem, m_Size);
#else
        delete []m_mem;
#endif
        m_mem = NULL;
    }
    if (m_words) {
        delete []m_words;
        m_words = NULL;
    }
    m_SimbolMap.clear();
}

bool
CPinyinTrie::load(const char *fname)
{
    free();

    bool suc = false;
    int fd = open(fname, O_RDONLY);
    if (fd == -1) return false;

    suc = read (fd, &m_Size, sizeof(unsigned int)) > 0;
#ifdef HAVE_SYS_MMAN_H
    suc = suc && ((m_mem = (char *) mmap (NULL, m_Size+sizeof(unsigned int), PROT_READ, MAP_SHARED, fd, 0))
                  != MAP_FAILED);
    m_mem += sizeof(unsigned int);
#else
    suc = suc && ((m_mem = new char [m_Size]) != NULL);
    suc = suc && (read (fd, m_mem, m_Size) > 0);
#endif
    close(fd);

    suc = suc && ((m_words = new TWCHAR*[getWordCount()]) != NULL);

    if (suc) {
        TWCHAR *p = (TWCHAR *)(m_mem + getStringOffset());
        for (int i=0, sz=getWordCount(); i < sz; ++i) {
            m_words[i] = p;
            while (*p++)
                ;
        }
        for (unsigned i=1; i < 100; ++i) {
            if (*m_words[i] != WCH_NULL && *m_words[i] != WCH_LESSTHAN)
                m_SimbolMap[wstring(m_words[i])] = i;
        }
    }
    return suc;
}