| 826 | |
| 827 | template <class TDescriptor, class F> |
| 828 | void TemplatedDatabase<TDescriptor, F>::queryKL(const BowVector& vec, |
| 829 | QueryResults& ret, |
| 830 | int max_results, |
| 831 | int max_id) const { |
| 832 | BowVector::const_iterator vit; |
| 833 | typename IFRow::const_iterator rit; |
| 834 | |
| 835 | std::map<EntryId, double> pairs; |
| 836 | std::map<EntryId, double>::iterator pit; |
| 837 | |
| 838 | for (vit = vec.begin(); vit != vec.end(); ++vit) { |
| 839 | const WordId word_id = vit->first; |
| 840 | const WordValue& vi = vit->second; |
| 841 | |
| 842 | const IFRow& row = m_ifile[word_id]; |
| 843 | |
| 844 | // IFRows are sorted in ascending entry_id order |
| 845 | |
| 846 | for (rit = row.begin(); rit != row.end(); ++rit) { |
| 847 | const EntryId entry_id = rit->entry_id; |
| 848 | const WordValue& wi = rit->word_weight; |
| 849 | |
| 850 | if ((int)entry_id < max_id || max_id == -1) { |
| 851 | double value = 0; |
| 852 | if (vi != 0 && wi != 0) value = vi * log(vi / wi); |
| 853 | |
| 854 | pit = pairs.lower_bound(entry_id); |
| 855 | if (pit != pairs.end() && !(pairs.key_comp()(entry_id, pit->first))) { |
| 856 | pit->second += value; |
| 857 | } else { |
| 858 | pairs.insert(pit, std::map<EntryId, double>::value_type(entry_id, value)); |
| 859 | } |
| 860 | } |
| 861 | |
| 862 | } // for each inverted row |
| 863 | } // for each query word |
| 864 | |
| 865 | // resulting "scores" are now in [-X worst .. 0 best .. X worst] |
| 866 | // but we cannot make sure which ones are better without calculating |
| 867 | // the complete score |
| 868 | |
| 869 | // complete scores and move to vector |
| 870 | ret.reserve(pairs.size()); |
| 871 | for (pit = pairs.begin(); pit != pairs.end(); ++pit) { |
| 872 | EntryId eid = pit->first; |
| 873 | double value = 0.0; |
| 874 | |
| 875 | for (vit = vec.begin(); vit != vec.end(); ++vit) { |
| 876 | const WordValue& vi = vit->second; |
| 877 | const IFRow& row = m_ifile[vit->first]; |
| 878 | |
| 879 | if (vi != 0) { |
| 880 | if (row.end() == find(row.begin(), row.end(), eid)) { |
| 881 | value += vi * (log(vi) - GeneralScoring::LOG_EPS); |
| 882 | } |
| 883 | } |
| 884 | } |
| 885 | |