ngram 的数据结构

Question

我在 Javascript 中构建了一个 ngram 模型实现，效果很好。但是，我希望更改我的数据结构，这样我就不必在每次观察到新的 word/character 时都遍历所有历史记录。

在这里，我获取一个种子文本并使用它来构建阶数为 2 的 ngram。

  var ngrams = {};
  var order = 2;
  var seedtext = "adadwsdawdsadawdsadadasdwdadaaasdsadsdadwdasdasd";
  
 build();
  
  function build(){
   
      for (var i = 0; i < seedtext.length - order; i++) {
        var gram = seedtext.substring(i, i + order);
        var next = seedtext.charAt(i + order);

        if (!ngrams.hasOwnProperty(gram)) {
          ngrams[gram] = [];
        }
        
        ngrams[gram].push(next);
      }
  }
  
  console.log(ngrams);
  console.log(ngrams["wd"]);

我希望有一个数据结构来保存每个观察到的模式的记录（对于给定的顺序。每个观察到的模式都应该有一个下一个可能的观察及其计数。

例如，如果您运行下面的代码，可以看到这样的输出：

[object Object] {
  aa: ["a", "s"],
  ad: ["a", "w", "a", "a", "a", "a", "s", "w"],
  as: ["d", "d", "d", "d"],
  aw: ["d", "d"],
  da: ["d", "w", "w", "d", "s", "d", "a", "d", "s", "s"],
  ds: ["a", "a", "a", "d"],
  dw: ["s", "d", "d"],
  sa: ["d", "d", "d"],
  sd: ["a", "w", "s", "a", "a"],
  wd: ["s", "s", "a", "a"],
  ws: ["d"]
}

["s", "s", "a", "a"]

现在，如果我们以"ad"为例：ngrams["ad"]，我们得到["a", "w", "a", "a", "a", "a", "s", "w"]。

显然，在 ad 之后我们可以得到 w、a 或 s。

我想对字母进行分组，以便 ngrams["ad"] returns 类似于：

{a: 5
w: 2
s :1}

请注意，它们是按顺序排列的，因此最常出现的字母及其计数位于顶部。

我希望能够像这样访问数据（例如）：

ngrams["ad"].a;
ngrams["ad"].w;
ngrams["ad"].s;

并为 a 返回 5，为 w 返回 2，为 s 返回 1。

我还希望能够在再次观察到先前看到的模式时增加值...我还希望能够删除模式。

有什么想法吗？

Answer 1

这是一个工作版本。您可以添加另一个对象来存储其中下一个字符的计数，而不是数组。

        var ngrams = {};
  var order = 2;
  var seedtext = "adadwsdawdsadawdsadadasdwdadaaasdsadsdadwdasdasd";
  
 build();
  
  function build(){
   
      for (var i = 0; i < seedtext.length - order; i++) {
        var gram = seedtext.substring(i, i + order);
        var next = seedtext.charAt(i + order);

        if (!ngrams.hasOwnProperty(gram)) {
          ngrams[gram] = {};
        }
        
        if (!ngrams[gram].hasOwnProperty(next)) {
          ngrams[gram][next] = 0;
        }

        ngrams[gram][next] += 1;
      }
  }
  
  console.log(ngrams);
  console.log(ngrams["wd"]);

ngram 的数据结构

Data structure for ngrams

javascript

data-structures

n-gram