diff options
author | John Wiegley <johnw@newartisans.com> | 2010-03-07 22:53:57 -0500 |
---|---|---|
committer | John Wiegley <johnw@newartisans.com> | 2010-03-08 01:11:55 -0500 |
commit | 1bf0220f246c5e984d9a43e5d8b3979b9091bc5a (patch) | |
tree | 710291f43415b9aed741a948ee8687316df13bda /src/lookup.cc | |
parent | e070cdfc8ddcf9d6a25b593502f1c5ade56c849c (diff) | |
download | fork-ledger-1bf0220f246c5e984d9a43e5d8b3979b9091bc5a.tar.gz fork-ledger-1bf0220f246c5e984d9a43e5d8b3979b9091bc5a.tar.bz2 fork-ledger-1bf0220f246c5e984d9a43e5d8b3979b9091bc5a.zip |
Added experimental account lookup logic
This is used by the "xact" command, and the CSV importer. It is very
slow O(xacts*records).
Diffstat (limited to 'src/lookup.cc')
-rw-r--r-- | src/lookup.cc | 296 |
1 files changed, 296 insertions, 0 deletions
diff --git a/src/lookup.cc b/src/lookup.cc new file mode 100644 index 00000000..d2056718 --- /dev/null +++ b/src/lookup.cc @@ -0,0 +1,296 @@ +/* + * Copyright (c) 2003-2010, John Wiegley. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * - 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. + * + * - Neither the name of New Artisans LLC nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS 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 COPYRIGHT + * OWNER OR 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. + */ + +#include <system.hh> + +#include "lookup.h" +#include "unistring.h" + +namespace ledger { + +namespace { + typedef std::pair<xact_t *, int> score_entry_t; + typedef std::deque<score_entry_t> scorecard_t; + typedef std::map<uint32_t, std::size_t> char_positions_map; + + struct score_sorter { + bool operator()(const score_entry_t& left, + const score_entry_t& right) const { + return left.second > right.second; + } + }; + + typedef std::map<account_t *, int> account_use_map; + typedef std::pair<account_t *, int> account_use_pair; + typedef std::vector<account_use_pair> account_use_vector; + + struct usage_sorter { + bool operator()(const account_use_pair& left, + const account_use_pair& right) const { + return left.second > right.second; + } + }; +} + +std::pair<xact_t *, account_t *> +lookup_probable_account(const string& ident, + xacts_iterator& iter_func, + account_t * ref_account) +{ + scorecard_t scores; + +#if !defined(HAVE_BOOST_REGEX_UNICODE) + string lident = ident; + to_lower(lident); + unistring lowered_ident(lident); +#else + // jww (2010-03-07): Not yet implemented + unistring lowered_ident(ident); +#endif + + DEBUG("lookup.account", + "Looking up identifier '" << lowered_ident.extract() << "'"); +#if defined(DEBUG_ON) + if (ref_account != NULL) + DEBUG("lookup.account", + " with reference account: " << ref_account->fullname()); +#endif + + while (xact_t * xact = iter_func()) { + // Only consider transactions from the last two years (jww (2010-03-07): + // make this an option) + if ((CURRENT_DATE() - xact->date()).days() > 700) + continue; + + // An exact match is worth a score of 100 + if (ident == xact->payee) { + DEBUG("lookup", " we have an exact match, score = 100"); + scores.push_back(score_entry_t(xact, 100)); + break; + } + +#if !defined(HAVE_BOOST_REGEX_UNICODE) + string payee = xact->payee; + to_lower(payee); + unistring value_key(payee); +#else + // jww (2010-03-07): Not yet implemented + unistring value_key(xact->payee); +#endif + + DEBUG("lookup", "Considering payee: " << value_key.extract()); + + std::size_t index = 0; + std::size_t last_match_pos = unistring::npos; + int bonus = 0; + int score = 0; + std::size_t pos; + char_positions_map positions; + + // Walk each letter in the source identifier + foreach (const uint32_t& ch, lowered_ident.utf32chars) { + int addend = 0; + + pos = value_key.find(ch); + + // If it occurs in the same order as the source identifier -- that is, + // without intervening letters to break the pattern -- it's worth 10 + // points. Plus, an extra point is added for every letter in chains of + // 3 or more. + + bool added_bonus = false; + if (pos == last_match_pos + 1) { + DEBUG("lookup", + " char " << index << " in-sequence match with bonus " << bonus); + addend += 10; + if (bonus > 2) + addend += bonus - 2; + bonus++; + added_bonus = true; + + last_match_pos = pos; + } + + // If it occurs in the same general sequence as the source identifier, + // it's worth 5 points, plus an extra point if it's within the next 3 + // characters, and an extra point if it's preceded by a non-alphabetic + // character. + // + // If the letter occurs at all in the target identifier, it's worth 1 + // point, plus an extra point if it's within 3 characters, and an extra + // point if it's preceded by a non-alphabetic character. + + else if (pos != unistring::npos) { + // Ensure that a letter which has been matched is not matched twice, + // so that the two x's of Exxon don't both match to the single x in + // Oxford. + char_positions_map::iterator pi = positions.find(ch); + if (pi != positions.end()) { + while (pi != positions.end() && + pos != unistring::npos && pos <= (*pi).second && + (*pi).second + 1 < value_key.length()) { + pos = value_key.find(ch, (*pi).second + 1); + } + } + + if (pos != unistring::npos) { + bool in_order_match = (last_match_pos != unistring::npos && + pos > last_match_pos); + DEBUG("lookup", " char " << index << " " << + (in_order_match ? "in-order" : "out-of-order") + << " match" << (in_order_match && pos - index < 3 ? + " with proximity bonus of 1" : "")); + + if (pi != positions.end()) + (*pi).second = pos; + else + positions.insert(char_positions_map::value_type(ch, pos)); + + if (pos < index) + addend += 1; + else + addend += 5; + + if (in_order_match && pos - index < 3) + addend++; + +#if !defined(HAVE_BOOST_REGEX_UNICODE) + if (pos == 0 || (pos > 0 && !std::isalnum(value_key[pos - 1]))) + addend++; +#else + // jww (2010-03-07): Not yet implemented +#endif + + last_match_pos = pos; + } else { + last_match_pos = unistring::npos; + + DEBUG("lookup", " char " << index << " does not match here"); + addend--; + } + } + + // If the letter does not appear at all, decrease the score by 1 + + else { + last_match_pos = unistring::npos; + + DEBUG("lookup", " char " << index << " does not match"); + addend--; + } + + // Finally, decay what is to be added to the score based on its position + // in the word. Since credit card payees in particular often share + // information at the end (such as the location where the purchase was + // made), we want to give much more credence to what occurs at the + // beginning. Every 5 character positions from the beginning becomes a + // divisor for the addend. + + if ((int(index / 5) + 1) > 1) { + DEBUG("lookup", + " discounting the addend by / " << (int(index / 5) + 1)); + addend = int(double(addend) / (int(index / 5) + 1)); + } + + DEBUG("lookup", " final addend is " << addend); + score += addend; + DEBUG("lookup", " score is " << score); + + if (! added_bonus) + bonus = 0; + + index++; + } + + scores.push_back(score_entry_t(xact, score)); + } + + // Sort the results by descending score, then look at every account ever + // used among the top ten. Rank these by number of times used. Lastly, + // "decay" any latter accounts, so that we give recently used accounts a + // slightly higher rating in case of a tie. + + std::stable_sort(scores.begin(), scores.end(), score_sorter()); + + account_use_map account_usage; + + scorecard_t::iterator si = scores.begin(); + + int decay = 0; + xact_t * best_xact = si != scores.end() ? (*si).first : NULL; + + for (int i = 0; i < 5 && si != scores.end(); i++, si++) { + DEBUG("lookup.account", + "Payee: " << std::setw(5) << std::right << (*si).second << + " - " << (*si).first->payee); + + // Only consider payees with a score of 20 or greater + if ((*si).second >= 50) { + foreach (post_t * post, (*si).first->posts) { + if (! post->has_flags(ITEM_TEMP | ITEM_GENERATED) && + post->account != ref_account && + ! post->account->has_flags(ACCOUNT_TEMP | ACCOUNT_GENERATED)) { + account_use_map::iterator x = account_usage.find(post->account); + if (x == account_usage.end()) + account_usage.insert(account_use_pair(post->account, + ((*si).second - decay))); + else + (*x).second += ((*si).second - decay); + } + decay++; + } + } + } + + if (account_usage.size() > 0) { + account_use_vector flat_account_usage(account_usage.begin(), + account_usage.end()); + + std::stable_sort(flat_account_usage.begin(), flat_account_usage.end(), + usage_sorter()); + +#if defined(DEBUG_ON) + if (SHOW_DEBUG("lookup.account")) { + foreach (account_use_pair& value, flat_account_usage) { + DEBUG("lookup.account", + "Account: " << value.second << " - " << value.first->fullname()); + } + } +#endif + + return std::pair<xact_t *, account_t *>(best_xact, + flat_account_usage.front().first); + } else { + return std::pair<xact_t *, account_t *>(best_xact, NULL); + } +} + +} // namespace ledger |