path: root/sa-extract/precomputation.pyx

# precomputes a set of collocations by advancing over the text.
# warning: nasty C code

import log
import monitor

cimport csuf
cimport cdat
cimport cintlist

from libc.stdio cimport FILE, fopen, fread, fwrite, fclose
from libc.stdlib cimport malloc, realloc, free
from libc.string cimport memset, memcpy

cdef struct _Trie_Node  # forward decl

cdef struct _Trie_Edge:
  int val
  _Trie_Node* node
  _Trie_Edge* bigger
  _Trie_Edge* smaller

cdef struct _Trie_Node:
  _Trie_Edge* root
  int* arr
  int arr_len

cdef _Trie_Node* new_trie_node():
  cdef _Trie_Node* node
  node = <_Trie_Node*> malloc(sizeof(_Trie_Node))
  node.root = NULL
  node.arr_len = 0
  node.arr = <int*> malloc(sizeof(0*sizeof(int)))
  return node

cdef _Trie_Edge* new_trie_edge(int val):
  cdef _Trie_Edge* edge
  edge = <_Trie_Edge*> malloc(sizeof(_Trie_Edge))
  edge.node = new_trie_node()
  edge.bigger = NULL
  edge.smaller = NULL
  edge.val = val
  return edge

cdef free_trie_node(_Trie_Node* node):
  if node != NULL:
    free_trie_edge(node.root)
    free(node.arr)

cdef free_trie_edge(_Trie_Edge* edge):
  if edge != NULL:
    free_trie_node(edge.node)
    free_trie_edge(edge.bigger)
    free_trie_edge(edge.smaller)

cdef _Trie_Node* trie_find(_Trie_Node* node, int val):
  cdef _Trie_Edge* cur
  cur = node.root
  while cur != NULL and cur.val != val:
    if val > cur.val:
      cur = cur.bigger
    elif val < cur.val:
      cur = cur.smaller
  if cur == NULL:
    return NULL
  else:
    return cur.node

cdef trie_node_data_append(_Trie_Node* node, int val):
  cdef int new_len
  new_len = node.arr_len + 1
  node.arr = <int*> realloc(node.arr, new_len*sizeof(int))
  node.arr[node.arr_len] = val
  node.arr_len = new_len

cdef trie_node_data_extend(_Trie_Node* node, int* vals, int num_vals):
  cdef int new_len
  new_len = node.arr_len + num_vals
  node.arr = <int*> realloc(node.arr, new_len*sizeof(int))
  memcpy(node.arr + node.arr_len, vals, num_vals*sizeof(int))
  node.arr_len = new_len


cdef _Trie_Node* trie_insert(_Trie_Node* node, int val):
  cdef _Trie_Edge** cur
  cur = &node.root
  while cur[0] != NULL and cur[0].val != val:
    if val > cur[0].val:
      cur = &cur[0].bigger
    elif val < cur[0].val:
      cur = &cur[0].smaller
  if cur[0] == NULL:
    cur[0] = new_trie_edge(val)
  return cur[0].node

cdef trie_node_to_map(_Trie_Node* node, result, prefix, int include_zeros):
  cdef cintlist.CIntList arr

  if include_zeros or node.arr_len > 0:
    arr = cintlist.CIntList()
    free(arr.arr)
    arr.arr = <int*> malloc(node.arr_len * sizeof(int))
    memcpy(arr.arr, node.arr, node.arr_len * sizeof(int))
    arr.len = node.arr_len
    arr.size = node.arr_len
    result[prefix] = arr
  trie_edge_to_map(node.root, result, prefix, include_zeros)

cdef trie_edge_to_map(_Trie_Edge* edge, result, prefix, int include_zeros):
  if edge != NULL:
    trie_edge_to_map(edge.smaller, result, prefix, include_zeros)
    trie_edge_to_map(edge.bigger, result, prefix, include_zeros)
    prefix = prefix + (edge.val,)
    trie_node_to_map(edge.node, result, prefix, include_zeros)

cdef class TrieMap:

  cdef _Trie_Node** root
  cdef int V

  def __init__(self, alphabet_size):
    self.V = alphabet_size
    self.root = <_Trie_Node**> malloc(self.V * sizeof(_Trie_Node*))
    memset(self.root, 0, self.V * sizeof(_Trie_Node*))


  def __dealloc__(self):
    cdef int i
    for i from 0 <= i < self.V:
      if self.root[i] != NULL:
        free_trie_node(self.root[i])
    free(self.root)


  def insert(self, pattern):
    cdef int* p
    cdef int i, l
    l = len(pattern)
    p = <int*> malloc(l*sizeof(int))
    for i from 0 <= i < l:
      p[i] = pattern[i]
    self._insert(p,l)
    free(p)


  cdef _Trie_Node* _insert(self, int* pattern, int pattern_len):
    cdef int i
    cdef _Trie_Node* node
    if self.root[pattern[0]] == NULL:
      self.root[pattern[0]] = new_trie_node()
    node = self.root[pattern[0]]
    for i from 1 <= i < pattern_len:
      node = trie_insert(node, pattern[i])
    return node

  def contains(self, pattern):
    cdef int* p
    cdef int i, l
    cdef _Trie_Node* node
    l = len(pattern)
    p = <int*> malloc(l*sizeof(int))
    for i from 0 <= i < l:
      p[i] = pattern[i]
    node = self._contains(p,l)
    free(p)
    if node == NULL:
      return False
    else:
      return True

  cdef _Trie_Node* _contains(self, int* pattern, int pattern_len):
    cdef int i
    cdef _Trie_Node* node
    node = self.root[pattern[0]]
    i = 1
    while node != NULL and i < pattern_len:
      node = trie_find(node, pattern[i])
      i = i+1
    return node

  def toMap(self, flag):
    cdef int i, include_zeros

    if flag:
      include_zeros=1
    else:
      include_zeros=0
    result = {}
    for i from 0 <= i < self.V:
      if self.root[i] != NULL:
        trie_node_to_map(self.root[i], result, (i,), include_zeros)
    return result


cdef class Precomputation:

#  Defined in .pxd file, here for reference:
#  cdef int precompute_rank
#  cdef int precompute_secondary_rank
#  cdef int max_length
#  cdef int max_nonterminals
#  cdef int train_max_initial_size
#  cdef int train_min_gap_size
#  cdef precomputed_index
#  cdef precomputed_collocations

  def __init__(self, filename, sa=None, precompute_rank=1000, precompute_secondary_rank=20, max_length=5, 
        max_nonterminals=2, train_max_initial_size=10, train_min_gap_size=2, from_binary=False):
    self.precompute_rank = precompute_rank
    self.precompute_secondary_rank = precompute_secondary_rank
    self.max_length = max_length
    self.max_nonterminals = max_nonterminals
    self.train_max_initial_size = train_max_initial_size
    self.train_min_gap_size = train_min_gap_size
    if from_binary:
      self.read_binary(filename)
    else:
      self.precompute(filename, sa)


  def read_binary(self, filename):
    cdef FILE* f
    cdef bytes bfilename = filename
    cdef char* cfilename = bfilename
    f = fopen(cfilename, "r")
    fread(&(self.precompute_rank), sizeof(int), 1, f)
    fread(&(self.precompute_secondary_rank), sizeof(int), 1, f)
    fread(&(self.max_length), sizeof(int), 1, f)
    fread(&(self.max_nonterminals), sizeof(int), 1, f)
    fread(&(self.train_max_initial_size), sizeof(int), 1, f)
    fread(&(self.train_min_gap_size), sizeof(int), 1, f)
    self.precomputed_index = self.read_map(f)
    self.precomputed_collocations = self.read_map(f)
    fclose(f)


  def write_binary(self, filename):
    cdef FILE* f
    cdef bytes bfilename = filename
    cdef char* cfilename = bfilename

    f = fopen(cfilename, "w")
    fwrite(&(self.precompute_rank), sizeof(int), 1, f)
    fwrite(&(self.precompute_secondary_rank), sizeof(int), 1, f)
    fwrite(&(self.max_length), sizeof(int), 1, f)
    fwrite(&(self.max_nonterminals), sizeof(int), 1, f)
    fwrite(&(self.train_max_initial_size), sizeof(int), 1, f)
    fwrite(&(self.train_min_gap_size), sizeof(int), 1, f)
    self.write_map(self.precomputed_index, f)
    self.write_map(self.precomputed_collocations, f)
    fclose(f)


  cdef write_map(self, m, FILE* f):
    cdef int i, N
    cdef cintlist.CIntList arr

    N = len(m)
    fwrite(&(N), sizeof(int), 1, f)
    for pattern, val in m.iteritems():
      N = len(pattern)
      fwrite(&(N), sizeof(int), 1, f)
      for word_id in pattern:
        i = word_id
        fwrite(&(i), sizeof(int), 1, f)
      arr = val
      arr.write_handle(f)


  cdef read_map(self, FILE* f):
    cdef int i, j, k, word_id, N
    cdef cintlist.CIntList arr

    m = {}
    fread(&(N), sizeof(int), 1, f)
    for j from 0 <= j < N:
      fread(&(i), sizeof(int), 1, f)
      key = ()
      for k from 0 <= k < i:
        fread(&(word_id), sizeof(int), 1, f)
        key = key + (word_id,)
      arr = cintlist.CIntList()
      arr.read_handle(f)
      m[key] = arr
    return m


  def precompute(self, filename, sa):
    cdef int i, l, N, max_pattern_len, i1, l1, i2, l2, i3, l3, ptr1, ptr2, ptr3, is_super, sent_count, max_rank
    cdef csuf.SuffixArray sarray
    cdef cdat.DataArray darray
    cdef cintlist.CIntList data, queue, cost_by_rank, count_by_rank
    cdef TrieMap frequent_patterns, super_frequent_patterns, collocations
    cdef _Trie_Node* node

    sarray = sa
    darray = sarray.darray
    data = darray.data

    frequent_patterns = TrieMap(len(darray.id2word))
    super_frequent_patterns = TrieMap(len(darray.id2word))
    collocations = TrieMap(len(darray.id2word))

    I_set = set()
    J_set = set()
    J2_set = set()
    IJ_set = set()
    pattern_rank = {}

    log.writeln("Precomputing frequent intersections\n", 1)
    start_time = monitor.cpu()

    max_pattern_len = 0
    if filename is not None:
      precompute_file = open(filename)
      for rank, line in enumerate(precompute_file):
        if rank >= self.precompute_rank:
          break
        phrase_words = line.split()[2:]
        phrase = ()
        for word in phrase_words:
          phrase = phrase + (darray.word2id[word],)
        max_pattern_len = max(max_pattern_len, len(phrase))
        frequent_patterns.insert(phrase)
        I_set.add(phrase)
        pattern_rank[phrase] = rank
        if rank < self.precompute_secondary_rank:
          super_frequent_patterns.insert(phrase)
          J_set.add(phrase)
      precompute_file.close()

    queue = cintlist.CIntList(increment=1000)

    log.writeln("  Computing inverted indexes...", 1)
    N = len(data)
    for i from 0 <= i < N:
      sa_word_id = data.arr[i]
      if sa_word_id == 1:
        queue._append(-1)
      else:
        for l from 1 <= l <= max_pattern_len:
          node = frequent_patterns._contains(data.arr+i, l)
          if node == NULL:
            break
          queue._append(i)
          queue._append(l)
          trie_node_data_append(node, i)

    log.writeln("  Computing collocations...", 1)
    N = len(queue)
    ptr1 = 0
    sent_count = 0
    while ptr1 < N:  # main loop
      i1 = queue.arr[ptr1]
      if i1 > -1:
        l1 = queue.arr[ptr1+1]
        ptr2 = ptr1 + 2
        while ptr2 < N:
          i2 = queue.arr[ptr2]
          if i2 == -1 or i2 - i1 >= self.train_max_initial_size:
            break
          l2 = queue.arr[ptr2+1]
          if i2 - i1 - l1 >= self.train_min_gap_size and i2 + l2 - i1 <= self.train_max_initial_size and l1+l2+1 <= self.max_length:
            node = collocations._insert(data.arr+i1, l1)
            node = trie_insert(node, -1)
            for i from i2 <= i < i2+l2:
              node = trie_insert(node, data.arr[i])
            trie_node_data_append(node, i1)
            trie_node_data_append(node, i2)
            if super_frequent_patterns._contains(data.arr+i2, l2) != NULL:
              if super_frequent_patterns._contains(data.arr+i1, l1) != NULL:
                is_super = 1
              else:
                is_super = 0
              ptr3 = ptr2 + 2
              while ptr3 < N:
                i3 = queue.arr[ptr3]
                if i3 == -1 or i3 - i1 >= self.train_max_initial_size:
                  break
                l3 = queue.arr[ptr3+1]
                if i3 - i2 - l2 >= self.train_min_gap_size and i3 + l3 - i1 <= self.train_max_initial_size and l1+l2+l3+2 <= self.max_length:
                  if is_super or super_frequent_patterns._contains(data.arr+i3, l3) != NULL:
                    node = collocations._insert(data.arr+i1, l1)
                    node = trie_insert(node, -1)
                    for i from i2 <= i < i2+l2:
                      node = trie_insert(node, data.arr[i])
                    node = trie_insert(node, -1)
                    for i from i3 <= i < i3+l3:
                      node = trie_insert(node, data.arr[i])
                    trie_node_data_append(node, i1)
                    trie_node_data_append(node, i2)
                    trie_node_data_append(node, i3)
                ptr3 = ptr3 + 2
          ptr2 = ptr2 + 2
        ptr1 = ptr1 + 2
      else:
        sent_count = sent_count + 1
        if sent_count % 10000 == 0:
          log.writeln("    %d sentences" % sent_count)
        ptr1 = ptr1 + 1

    self.precomputed_collocations = collocations.toMap(False)
    self.precomputed_index = frequent_patterns.toMap(True)

    x = 0
    for pattern1 in J_set:
      for pattern2 in J_set:
        if len(pattern1) + len(pattern2) + 1 < self.max_length:
          combined_pattern = pattern1 + (-1,) + pattern2
          J2_set.add(combined_pattern)

    for pattern1 in I_set:
      for pattern2 in I_set:
        x = x+1
        if len(pattern1) + len(pattern2) + 1 <= self.max_length:
          combined_pattern = pattern1 + (-1,) + pattern2
          IJ_set.add(combined_pattern)

    for pattern1 in I_set:
      for pattern2 in J2_set:
        x = x+2
        if len(pattern1) + len(pattern2) + 1<= self.max_length:
          combined_pattern = pattern1 + (-1,) + pattern2
          IJ_set.add(combined_pattern)
          combined_pattern = pattern2 + (-1,) + pattern1
          IJ_set.add(combined_pattern)

    N = len(pattern_rank)
    cost_by_rank = cintlist.CIntList(initial_len=N)
    count_by_rank = cintlist.CIntList(initial_len=N)
    for pattern, arr in self.precomputed_collocations.iteritems():
      if pattern not in IJ_set:
        s = ""
        for word_id in pattern:
          if word_id == -1:
            s = s + "X "
          else:
            s = s + darray.id2word[word_id] + " "
        log.writeln("ERROR: unexpected pattern %s in set of precomputed collocations" % (s), 1)
      else:
        chunk = ()
        max_rank = 0
        arity = 0
        for word_id in pattern:
          if word_id == -1:
            max_rank = max(max_rank, pattern_rank[chunk])
            arity = arity + 1
            chunk = ()
          else:
            chunk = chunk + (word_id,)
        max_rank = max(max_rank, pattern_rank[chunk])
        cost_by_rank.arr[max_rank] = cost_by_rank.arr[max_rank] + (4*len(arr))
        count_by_rank.arr[max_rank] = count_by_rank.arr[max_rank] + (len(arr)/(arity+1))

    cumul_cost = 0
    cumul_count = 0
    for i from 0 <= i < N:
      cumul_cost = cumul_cost + cost_by_rank.arr[i]
      cumul_count = cumul_count + count_by_rank.arr[i]
      log.writeln("RANK %d\tCOUNT, COST: %d  %d\tCUMUL: %d, %d" % (i, count_by_rank.arr[i], cost_by_rank.arr[i], cumul_count, cumul_cost))

    num_found_patterns = len(self.precomputed_collocations)
    for pattern in IJ_set:
      if pattern not in self.precomputed_collocations:
        self.precomputed_collocations[pattern] = cintlist.CIntList()

    stop_time = monitor.cpu()
    log.writeln("Precomputed collocations for %d patterns out of %d possible (upper bound %d)" % (num_found_patterns,len(self.precomputed_collocations),x))
    log.writeln("Precomputed inverted index for %d patterns " % len(self.precomputed_index))
    log.writeln("Precomputation took %f seconds" % (stop_time - start_time))
    log.writeln("Detailed statistics:")