Fast Textual Data Processing using Hashed Strings

• Download source files - 3.04 Kb

Introduction

Strings are considered heavy nesting loop generators. Comparisons, searching, and sorting strings are considered time consuming operations. Indexing textual data is a good step, however setting searching key as string yields bad performance for search algorithms.

In this article we introduce an ADT abstracting strings with hash-codes. Comparisons will no more be done with byte comparisons. Each words in the alphabet will be assigned an invertible hash-code.

Hashing Function

Hashing functions aim to represent a collection of data in a single code. Codes may overlap, so a good hash function aims to minimise overlapping between codes. Systems using hashing should also manage overflow problems. What we represent here could be called as hashing. However, it is invertible and assures uniquness. Actually, it manages a numbering system for textual data.

Consider the word "baby", calculating hash-code is simply as converting from binary to decimal numbering systems. In this case, we convert from 26th numbring system to decimal, where 26 is the number of english alphbet characters.

("baba")₂₆=0x26⁰+1x26¹+0x26²+1x26³=(17626)₁₀

("babb")₂₆=1x26⁰+1x26¹+0x26²+1x26³=(17627)₁₀

This means that "baba" is less than "babb". Comparison is done with numbers. No more nesting loops is needed for comparisons.

Class hashedstring

class hashedstring

{

public:
    hashedstring():_pdata(0), _hashkey(0), _size(0){}
    hashedstring(const hashedstring& hstr):_pdata(strdup(hstr._pdata)), _
        hashkey(hstr._hashkey), _size(hstr._size){}
    hashedstring(const char* pdata):_pdata(strdup(pdata)), 
        _hashkey(0), _size(strlen(pdata))
    {
        _computehashkey();
    }
   
    hashedstring operator+(const hashedstring& s) const 
    {
        hashedstring rtn=*this;
        strcat(rtn._pdata, s._pdata);
        rtn._hashkey+=_hashkey*pow(26, s._size);
        rtn._size+=s._size;
        return rtn;
    }

 
    hashedstring operator+=(const hashedstring& s)
    { 
        strcat(_pdata, s._pdata);
        _hashkey=_hashkey*pow(26, s._size)+s._hashkey;
        _size+=s._size;
        return *this;
    }
    
    hashedstring operator=(const hashedstring& s) 
    {
        clear();
        _pdata=strdup(s._pdata);
        _hashkey+=s._hashkey;
        _size=s._size;
        return *this;
    }

 
    void clear()
    {
        if(_pdata)
            delete []_pdata;
        _pdata=0;
        _size=0;
        _hashkey=0;
    }

 
    ~hashedstring(){}
    
    operator const double() const {return _hashkey;}
    
    
protected:
    

    double _computehashkey()
    {
        unsigned int i=0;
        _hashkey=0;
        for(i=_size-1; i!=-1; i--)
            _hashkey+=(tolower(_pdata[i])-'a')*pow(26, _size-1-i);
        return _hashkey;
    }
    
    char* _pdata;
    double _hashkey;
    unsigned int _size;

};

Conclusions

Maintaining alphabet numbering system provides faster string processing. Calculating hash codes, an offline process, should be added in indexing huge textual data. Then the system will enjoy fast comparisons, search, and sort routines.

    
    hashedstring s1("baby");
    hashedstring s2("babybaba");
    hashedstring s3("babybabb");
    
    vprint(s1);
    
    s1+="baba";
    
    vprint(s1);
    vprint(s2);
    vprint(s3);
    
    vprint(s1<s2);
    vprint(s2<s3);
    vprint(s2==s3);
    
    vprint(s1==s2);

Results

    s1= 17626
    s1= 8054676578
    s2= 8054676578
    s3= 8054676579
    s1<s2= 0
    s2<s3= 1
    s2==s3= 0
    s1==s2= 1