Thread portable class Gate portable class Timer class Pool class Terimber 2.0 About C++

Downloads Products & Services Support Clients Open Source About Home / Open source / Terimber 2.0 fuzzyimpl.h Go to the documentation of this file. /* * The Software License * ================================================================================= * Copyright (c) 2003-.The Terimber Corporation. All rights reserved. * ================================================================================= * Redistributions of source code must retain the above copyright notice, * this list of conditions and the following disclaimer. * Redistributions in binary form must reproduce the above copyright notice, * this list of conditions and the following disclaimer in the documentation * and/or other materials provided with the distribution. * The end-user documentation included with the redistribution, if any, * must include the following acknowledgment: * "This product includes software developed by the Terimber Corporation." * ================================================================================= * THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESSED OR IMPLIED WARRANTIES, * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. * IN NO EVENT SHALL THE TERIMBER CORPORATION OR ITS CONTRIBUTORS BE LIABLE FOR * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * ================================================================================ */ #ifndef _terimber_fuzzyimpl_h_ #define _terimber_fuzzyimpl_h_ #include "fuzzy/fuzzyaccess.h" #include "base/map.h" #include "base/vector.h" #include "base/stack.h" #include "base/string.h" #include "smart/byterep.h" #include "tokenizer/tokenizer.h" BEGIN_TERIMBER_NAMESPACE #pragma pack(4) #define MAX_TOKEN_LENGTH (size_t)64 #define MAX_PHRASE_TOKENS (size_t)64 class metaphone_key { public: metaphone_key() : _array(0), _length(0) { } inline bool operator<(const metaphone_key& x) const { if (!_length) return x._length != 0; else if (!x._length) return false; else { ub4_t min_len = __min(_length, x._length); int res = memcmp(_array, x._array, min_len); return res != 0 ? res < 0 : _length < x._length; } } ub1_t* _array; ub4_t _length; }; class metaphone_entry { public: metaphone_entry(size_t mpk ) : _mpk(mpk), _ref(1) { } size_t _mpk; size_t _ref; }; class reflection_key { public: enum reflection_size { REFSIZE = 17, REFMAX = 0xFF }; typedef ub1_t reflection_bytes_t[REFSIZE]; public: reflection_key() { memset(_array, 0, REFSIZE * sizeof(ub1_t)); } inline bool operator<(const reflection_key& x) const { return memcmp(_array, x._array, REFSIZE * sizeof(ub1_t)) < 0; } reflection_bytes_t _array; }; class reflection_entry { public: reflection_entry(size_t rpk) : _rpk(rpk), _ref(1) { } size_t _rpk; size_t _ref; }; typedef map< metaphone_key, metaphone_entry > metaphone_entry_t; typedef metaphone_entry_t::iterator metaphone_entry_iter_t; typedef metaphone_entry_t::const_iterator metaphone_entry_citer_t; typedef map< reflection_key, reflection_entry > reflection_entry_t; typedef reflection_entry_t::iterator reflection_entry_iter_t; typedef reflection_entry_t::const_iterator reflection_entry_citer_t; class word_key { public: word_key( const char* str, size_t len ) : _str(str), _len(len) { } inline bool operator<(const word_key& x) const { if (!_str) return x._str != 0; else if (!x._str) return false; else { size_t min_len = __min(_len, x._len); int res = str_template::strnocasecmp(_str, x._str, min_len); return res != 0 ? res < 0 : _len < x._len; } } const char* _str; size_t _len; }; class word_entry { public: word_entry( size_t vpk, metaphone_entry_iter_t miter ) : _vpk(vpk), _miter(miter), _ref(1) { } size_t _vpk; metaphone_entry_iter_t _miter; size_t _ref; }; typedef map< word_key, word_entry > word_entry_t; typedef word_entry_t::iterator word_entry_iter_t; typedef map< size_t, word_entry_iter_t > vpk_word_entry_iter_t; typedef map< size_t, word_entry_iter_t, less< size_t >, true > mpk_word_entry_iter_t; class ngram_key { public: inline bool operator<(const ngram_key& x) const { if (!_length) return x._length != 0; else if (!x._length) return false; else { ub4_t min_len = (ub4_t)__min(_length, x._length); int res = memcmp(_array, x._array, min_len * sizeof(size_t)); return res != 0 ? res < 0 : _length < x._length; } } inline bool operator==(const ngram_key& x) const { if (_length != x._length) return false; else return memcmp(_array, x._array, _length * sizeof(size_t)) == 0; } size_t* _array; size_t _length; }; class ngram_entry { public: ngram_entry( size_t npk, reflection_entry_iter_t riter ) : _npk(npk), _riter(riter), _ref(1) { } size_t _npk; reflection_entry_iter_t _riter; ngram_key _origin; size_t _ref; }; typedef map< ngram_key, ngram_entry > ngram_entry_t; typedef ngram_entry_t::iterator ngram_entry_iter_t; typedef map< size_t, ngram_entry_iter_t > npk_ngram_entry_iter_t; typedef map< size_t, ngram_entry_iter_t, less< size_t >, true > rpk_ngram_entry_iter_t; class ngram_suggestions_info { public: ngram_suggestions_info(size_t vpk, size_t popularity, double score, size_t penalty ) : _vpk(vpk), _popularity(popularity), _score(score), _penalty(penalty) { } size_t _vpk; size_t _popularity; double _score; size_t _penalty; }; typedef _map< double, ngram_suggestions_info > sorted_ngram_suggestions_t; typedef sorted_ngram_suggestions_t::const_iterator sorted_ngram_suggestions_citer_t; class ngram_suggestions_iter_info { public: ngram_suggestions_iter_info(sorted_ngram_suggestions_citer_t begin, sorted_ngram_suggestions_citer_t end ) : _begin(begin), _current(begin), _end(end) { } sorted_ngram_suggestions_citer_t _begin; sorted_ngram_suggestions_citer_t _current; sorted_ngram_suggestions_citer_t _end; }; typedef _list< ngram_suggestions_iter_info > ngram_suggestions_iter_list_t; class string_desc { public: size_t _vpk; double _score; size_t _popularity; const char* _str; size_t _len; }; class fuzzy_matcher_impl : public fuzzy_matcher { class ngram_key_offset { public: ngram_key_offset(size_t offset, ngram_entry_iter_t iter ) : _offset(offset), _iter(iter), _pointer(0) { } ngram_key_offset(size_t offset, const ngram_key* pointer ) : _offset(offset), _pointer(pointer) { } inline bool operator<(const ngram_key_offset& x) const { if (_offset != x._offset) return _offset < x._offset; else { const ngram_key* this_ptr = 0; const ngram_key* x_ptr = 0; if (x._pointer) { assert(_pointer == 0); this_ptr = &_iter.key(); x_ptr = x._pointer; } else if (_pointer) { assert(x._pointer == 0); this_ptr = _pointer; x_ptr = &x._iter.key(); } else { assert(_pointer == 0); assert(x._pointer == 0); this_ptr = &_iter.key(); x_ptr = &x._iter.key(); } ub4_t min_len = (ub4_t)__min(this_ptr->_length, x_ptr->_length); assert(min_len > _offset); int res = memcmp(this_ptr->_array + _offset, x_ptr->_array + _offset, (min_len - _offset) * sizeof(size_t)); return res != 0 ? res < 0 : this_ptr->_length < x_ptr->_length; } } size_t _offset; ngram_entry_iter_t _iter; const ngram_key* _pointer; }; typedef map< ngram_key_offset, bool, less< ngram_key_offset >, true > ngram_key_offset_multimap_t; class candidate_info { public: candidate_info(double total_score, double intersection_score, size_t population, size_t word_penalty ) : _total_score(total_score), _intersection_score(intersection_score), _population(population), _word_penalty(word_penalty) { } double _total_score; double _intersection_score; size_t _population; size_t _word_penalty; }; typedef _map< ngram_key, candidate_info > candidates_container_t; typedef candidates_container_t::const_iterator candidates_container_citer_t; typedef _vector< candidates_container_citer_t > vector_container_citer_t; class candidate_sorter { class candidate_iter_less { public: bool operator()(const candidates_container_citer_t& x, const candidates_container_citer_t& y) const { return x->_total_score < y->_total_score; } }; public: candidate_sorter(const candidates_container_t& container, vector_container_citer_t& vec, byte_allocator& tmp ) { size_t len = container.size(); if (len > 1) { vec.resize(tmp, len); size_t index = 0; for (candidates_container_citer_t iter = container.begin(); iter != container.end(); ++iter, ++index) { vec[index] = iter; } candidate_iter_less pred; std::sort(vec.begin(), vec.end(), pred); } else if (len > 0) { vec.resize(tmp, 1); vec[0] = container.begin(); } } }; public: fuzzy_matcher_impl(size_t memory_usage ); virtual ~fuzzy_matcher_impl(); // methods virtual size_t add( const char* phrase, byte_allocator& all ); virtual bool remove( const char* phrase, byte_allocator& all ); virtual bool remove( size_t ident, byte_allocator& all ); virtual bool match( ngram_quality nq, phonetic_quality pq, const char* phrase, byte_allocator& all, byte_allocator& tmp, _list< const char* >& suggestions ) const; virtual bool match( ngram_quality nq, phonetic_quality fq, const char* phrase, byte_allocator& all, byte_allocator& tmp, _list< size_t >& suggestions ) const; virtual void reset(); private: bool _match ( ngram_quality nq, phonetic_quality fq, const char* phrase, byte_allocator& all, byte_allocator& tmp, candidates_container_t& candidates ) const; void partial_intersect(ngram_quality nq, phonetic_quality fq, const ngram_key& key, const ngram_key& key_origin, double score, size_t popularity, size_t word_penalty, byte_allocator& all, byte_allocator& tmp, candidates_container_t& candidate ) const; word_key reconstruct_string(const ngram_key& key, byte_allocator& tmp, bool preserve_case ) const; static word_key make_string_lower(const char* str, size_t len, byte_allocator& tmp ); static word_key make_string_lower(const char* str, size_t len, char* buf ); static double calculate_nkey_score(const ngram_key& key1, const ngram_key& key2 ); static double calculate_score(double phonetic_score, double intersection_score, size_t popularity, size_t penalty ); static ub4_t find_and_remove(const metaphone_key& key, ub1_t* array, ub4_t& len ); private: byte_repository_factory _memory_factory; tokenizer _tokenizer; unique_key_generator _vocabulary_pk_generator; unique_key_generator _ngram_pk_generator; unique_key_generator _metaphone_pk_generator; unique_key_generator _reflection_pk_generator; word_entry_t _word_vocabulary; vpk_word_entry_iter_t _vpk_word_vocabulary; metaphone_entry_t _metaphone_vocabulary; mpk_word_entry_iter_t _mpk_word_vocabulary; ngram_entry_t _ngram_vocabulary; npk_ngram_entry_iter_t _npk_ngram_vocabulary; reflection_entry_t _reflection_vocabulary; rpk_ngram_entry_iter_t _rpk_ngram_vocabulary; ngram_key_offset_multimap_t _ngram_partial_map; }; #pragma pack() END_TERIMBER_NAMESPACE #endif //_terimber_fuzzyimpl_h_

© Copyright Terimber 2003-.