Repository: bst-mug/acres

Issue:
Make `find_embeddings` faster
Ideas:
- Break down index.p into different files, one for each initial letter.
- Use tries.
- Reimplement from scratch.

Discussion:

Patch:
diff --git a/acres/evaluation/evaluation.py b/acres/evaluation/evaluation.py
index 09c345a..75c3425 100644
--- a/acres/evaluation/evaluation.py
+++ b/acres/evaluation/evaluation.py
@@ -62,20 +62,22 @@ def analyze(contextualized_acronym: topic_list.Acronym, true_expansions: Set[str
     """
     ret = {'found': False, 'correct': False, 'ignored': False}
 
-    left_context = text.context_ngram(contextualized_acronym.left_context, 3, True)
+    # Normalize context so that we can match it to the training data
+    left_context = text.clean(contextualized_acronym.left_context)
     acronym = contextualized_acronym.acronym
-    right_context = text.context_ngram(contextualized_acronym.right_context, 3, False)
-
-    logger.debug("%s => %s", acronym, true_expansions)
+    right_context = text.clean(contextualized_acronym.right_context)
 
     # Normalize true expansions so that we can match them to the training data
     true_expansions = set(map(text.clean, true_expansions))
 
+    # Remove context to improve cache hit
     # XXX We currently support context only for n-grams
-    if strategy != resolver.Strategy.NGRAM:
+    if strategy not in [resolver.Strategy.NGRAM, resolver.Strategy.FASTNGRAM]:
         left_context = ""
         right_context = ""
 
+    logger.debug("%s [%s] %s => %s", left_context, acronym, right_context, true_expansions)
+
     possible_expansions = resolver.cached_resolve(acronym, left_context, right_context, strategy)
 
     if possible_expansions:
diff --git a/acres/fastngram/fastngram.py b/acres/fastngram/fastngram.py
index 276b87d..c367784 100644
--- a/acres/fastngram/fastngram.py
+++ b/acres/fastngram/fastngram.py
@@ -2,10 +2,14 @@
 A faster version of n-gram matching that uses dictionaries for speed-up.
 """
 
+import logging
 from collections import OrderedDict
 from typing import List, Dict, Set, Tuple, Iterator
 
 from acres.preprocess import resource_factory
+from acres.util import text
+
+logger = logging.getLogger(__name__)
 
 
 class ContextMap:
@@ -14,6 +18,7 @@ class ContextMap:
     """
 
     def __init__(self) -> None:
+        # TODO Refactor as Dict[Tuple[str, str], Dict[int, Set[str]]], with int = freq
         self.map = {}  # type: Dict[Tuple[str, str], Set[str]]
 
     def add_context(self, center: str, left_context: str, right_context: str) -> None:
@@ -55,13 +60,24 @@ def expandn(acronym: str, left_context: str = "", right_context: str = "") -> It
     """
     model = resource_factory.get_fastngram()
 
-    # TODO support for n-grams (n > 1). May need an OrderedDict.
-    count_map = model[1]
-    for freq, context_map in count_map.items():
-        # TODO require a min_freq?
-        center_ngrams = context_map.centers(left_context, right_context)
-        for ngram in center_ngrams:
-            yield ngram
+    # Save previous expansions to avoid the same n-gram to be retrieve from different contexts.
+    previous_ngrams = set()
+
+    for size in range(7, 0, -2):
+        if size not in model:
+            continue
+
+        left = text.context_ngram(left_context, int(size / 2), True)
+        right = text.context_ngram(right_context, int(size / 2), False)
+
+        count_map = model[size]
+        for freq, context_map in count_map.items():
+            # TODO require a min_freq?
+            center_ngrams = context_map.centers(left, right)
+            for ngram in center_ngrams:
+                if ngram not in previous_ngrams:
+                    previous_ngrams.add(ngram)
+                    yield ngram
 
 
 def expand(acronym: str, left_context: str = "", right_context: str = "") -> List[str]:
@@ -74,9 +90,8 @@ def expand(acronym: str, left_context: str = "", right_context: str = "") -> Lis
     :return:
     """
     # Limit expansions while we don't use generators downstream
-    # TODO 1k may not be enough if we're not doing ANY filtering here (e.g. initial).
-    # https://github.com/bst-mug/acres/issues/28
-    limit = 1000
+    # TODO https://github.com/bst-mug/acres/issues/28
+    limit = 10000
     i = 0
     ret = []  # type: List[str]
     for ngram in expandn(acronym, left_context, right_context):
@@ -87,23 +102,76 @@ def expand(acronym: str, left_context: str = "", right_context: str = "") -> Lis
     return ret
 
 
+def baseline(acronym: str, left_context: str = "", right_context: str = "") -> List[str]:
+    """
+    A baseline method that expands only with unigrams.
+
+    :param acronym:
+    :param left_context:
+    :param right_context:
+    :return:
+    """
+    return expand(acronym, "", "")
+
+
 def optimizer(ngrams: Dict[str, int]) -> 'Dict[int, OrderedDict[int, ContextMap]]':
     """
     Create a search-optimized represenation of an ngram-list.
 
+    @todo Support assymetric n-grams.
+    @todo Support training contexts from the acronym.
+
     :param ngrams:
     :return:
     """
+    logger.info("Creating model for fastngram...")
+
     model = {}  # type: Dict[int, OrderedDict[int, ContextMap]]
 
     # Ensure ngrams are ordered by decreasing frequency.
     sorted_ngrams = sorted(ngrams.items(), key=lambda x: x[1], reverse=True)
 
     for ngram, freq in sorted_ngrams:
-        # size = len(ngram.split(" "))
+        tokens = ngram.split(" ")
+        ngram_size = len(tokens)
+
+        # Add n-grams with a decreasing central n-gram and increasing lateral context.
+        for i in range(ngram_size):
+            j = ngram_size - i
+            # Walk only until half.
+            if i >= j:
+                break
+            left = " ".join(tokens[0:i])
+            right = " ".join(tokens[j:ngram_size])
+            # TODO preserve list and intern strings
+            center = " ".join(tokens[i:j])
+            size = 1 + 2 * i  # n-gram size
+            _update_model(model, size, freq, center, left, right)
+
+    logger.info("Fastngram model created.")
+    return model
+
+
+def _update_model(model, size, freq, center, left_context, right_context):
+    """
+    Update the model with the given ngram.
+
+    :param model:
+    :param size:
+    :param freq:
+    :param center:
+    :param left_context:
+    :param right_context:
+    :return:
+    """
+    # Initialize context map if needed
+    if size in model and freq in model[size]:
+        context = model[size][freq]
+    else:
         context = ContextMap()
-        context.add_context(ngram, "", "")
-        model.setdefault(1, OrderedDict())
-        model[1][freq] = context
 
-    return model
+    # TODO Remove size dict, which is redundant with the context length.
+
+    context.add_context(center, left_context, right_context)
+    model.setdefault(size, OrderedDict())  # initialize dictionary count -> ContextMap if needed
+    model[size][freq] = context
diff --git a/acres/preprocess/resource_factory.py b/acres/preprocess/resource_factory.py
index 6f1d3fe..3c67ab0 100644
--- a/acres/preprocess/resource_factory.py
+++ b/acres/preprocess/resource_factory.py
@@ -315,9 +315,16 @@ def get_fastngram() -> 'Dict[int, OrderedDict[int, fastngram.ContextMap]]':
     global FAST_NGRAM
 
     if not FAST_NGRAM:
-        word_ngrams = get_word_ngrams()
-        logger.info("Optimizing ngrams...")
-        FAST_NGRAM = fastngram.optimizer(word_ngrams)
+        pickle_output_file = PICKLE_FOLDER + "fastngram-V2.p"
+
+        if not os.path.isfile(pickle_output_file):
+            _log_file_not_found(pickle_output_file)
+
+            fastngram_model = fastngram.optimizer(get_word_ngrams())
+            _dump(fastngram_model, pickle_output_file)
+
+        _log_file_found(pickle_output_file)
+        FAST_NGRAM = _load(pickle_output_file)
 
     return FAST_NGRAM
 
diff --git a/acres/resolution/resolver.py b/acres/resolution/resolver.py
index 162cafc..687bd8b 100644
--- a/acres/resolution/resolver.py
+++ b/acres/resolution/resolver.py
@@ -17,12 +17,14 @@ class Strategy(Enum):
     WORD2VEC = 2
     DICTIONARY = 3
     FASTNGRAM = 4
+    BASELINE = 5
 
 
 NGRAM_CACHE = {}  # type: Dict[Tuple, List[str]]
 WORD2VEC_CACHE = {}  # type: Dict[Tuple, List[str]]
 DICTIONARY_CACHE = {}  # type: Dict[Tuple, List[str]]
 FASTNGRAM_CACHE = {}  # type: Dict[Tuple, List[str]]
+BASELINE_CACHE = {}  # type: Dict[Tuple, List[str]]
 
 
 def cached_resolve(acronym: str, left_context: str, right_context: str,
@@ -43,7 +45,8 @@ def cached_resolve(acronym: str, left_context: str, right_context: str,
         Strategy.NGRAM: NGRAM_CACHE,
         Strategy.WORD2VEC: WORD2VEC_CACHE,
         Strategy.DICTIONARY: DICTIONARY_CACHE,
-        Strategy.FASTNGRAM: FASTNGRAM_CACHE
+        Strategy.FASTNGRAM: FASTNGRAM_CACHE,
+        Strategy.BASELINE: BASELINE_CACHE
     }
 
     cache = switcher.get(strategy)
@@ -96,6 +99,7 @@ def resolve(acronym: str, left_context: str, right_context: str, strategy: Strat
         Strategy.WORD2VEC: test.find_candidates,
         Strategy.DICTIONARY: dictionary.expand,
         Strategy.FASTNGRAM: fastngram.expand,
+        Strategy.BASELINE: fastngram.baseline
     }
 
     func = switcher.get(strategy)
diff --git a/acres/util/text.py b/acres/util/text.py
index c9c1e62..4865adf 100644
--- a/acres/util/text.py
+++ b/acres/util/text.py
@@ -191,6 +191,8 @@ def context_ngram(words: str, size: int, reverse: bool = False) -> str:
     :param reverse:
     :return:
     """
+    if size == 0:
+        return ""
     tokens = words.split(" ")
     return " ".join(tokens[-size:]) if reverse else " ".join(tokens[:size])
 


Test patch:
diff --git a/tests/conftest.py b/tests/conftest.py
index 7cce7bd..72323a1 100644
--- a/tests/conftest.py
+++ b/tests/conftest.py
@@ -1,4 +1,5 @@
 import os
+
 import pytest
 
 from acres.preprocess import resource_factory
@@ -56,8 +57,11 @@ def word_ngrams():
     old = resource_factory.WORD_NGRAMS
     resource_factory.WORD_NGRAMS = {"EKG": 500,
                                     "Elektrokardiogramm": 200,
-                                    "performed EKG yesterday": 50,
+                                    "performed EKG yesterday": 30,
                                     "performed Elektrokardiogramm yesterday": 20,
+                                    "performed Eakaga yesterday": 20,
+                                    "performed Echokardiogramm 1980": 20,
+                                    "scheduled Echokardiogramm yesterday": 20,
                                     "performed Elektro kardiogramm yesterday": 10,  # sic
                                     "performed Effusion yesterday": 5
                                     }
diff --git a/tests/fastngram/test_fastngram.py b/tests/fastngram/test_fastngram.py
index 36d7033..edf6d6d 100644
--- a/tests/fastngram/test_fastngram.py
+++ b/tests/fastngram/test_fastngram.py
@@ -1,6 +1,18 @@
-from acres.fastngram.fastngram import expand
+from acres.fastngram import fastngram
 
 
 def test_expand(word_ngrams):
-    expansions = expand("EKG")
+    expansions = fastngram.expand("EKG")
+    assert len(expansions) == 9
     assert "Elektrokardiogramm" in expansions
+    assert expansions[0] == "EKG"
+
+    expansions = fastngram.expand("EKG", "performed", "yesterday")
+    assert len(expansions) == 12
+    assert "Elektro kardiogramm" in expansions
+    assert expansions[0] == "EKG"
+
+
+def test_baseline(word_ngrams):
+    expansions = fastngram.baseline("EKG")
+    assert len(expansions) == 9
diff --git a/tests/util/test_text.py b/tests/util/test_text.py
index 8a37a8c..c2559fa 100644
--- a/tests/util/test_text.py
+++ b/tests/util/test_text.py
@@ -33,6 +33,17 @@ def test_transliterate_to_seven_bit():
     assert "AANGSTROEM" == acres.util.text.transliterate_to_seven_bit("ångström")
 
 
+def test_context_ngram():
+    ngram = "A B C D E F"
+    assert text.context_ngram(ngram, 3, True) == "D E F"
+    assert text.context_ngram(ngram, 1, True) == "F"
+    assert text.context_ngram(ngram, 0, True) == ""
+
+    assert text.context_ngram(ngram, 3, False) == "A B C"
+    assert text.context_ngram(ngram, 1, False) == "A"
+    assert text.context_ngram(ngram, 0, False) == ""
+
+
 def test_remove_duplicated_whitespaces():
     expected = "abc def ghi z"
     actual = acres.util.text.remove_duplicated_whitespaces("abc    def   ghi z")