JavaScript中数组键/值的单词频率

Question

我正在尝试在JavaScript上实现一段代码，以分析给定字符串中的单词/频率。我的目标是返回以下数组：

[{text: firstword, size:3 },{text:secondword , size:5 },{text: nword, size: 1},...]

我实现了以下代码，但是我内存不足，所以我不知道它是否正常。

function wordFrequency(txt){
    var wordArray = txt.split(/[ .?!,*'"]/);
    var newArray = [];
    $.each(wordArray, function (ix, word) {
        if (newArray.length >= 1){
            newArray.some(function (w){
                if (w.text === word){
                    w.size++;
                } else {
                    newArray.push({text: word, size: 1});
                }
            });
        } else {
            newArray.push({text: word, size: 1});
        }
    });
    return newArray;
}

- diegodacal

---

在我的控制台上没问题。 - Nickool

但它会有重复的结果。我尝试了这个：wordFrequency("negin!kjs$wkjh*df oiuw& skdjhh"); - Nickool

我正在尝试使用一大块文本，但每次都会出现内存不足的问题，即使在jsfiddle上也是如此。 :( - diegodacal

只需删除空格并再次尝试即可，我的意思是在这里：txt.split(/[ .?!,'"]/); 删除and并改为这个：txt.split(/[.?!,'"]/); - Nickool

除了我的答案之外，内存耗尽也是你的代码不正常的一个很好的指标。 - LJᛃ

Answer 1

创建一个直接从单词到频率的映射，然后再将其转换为数组结构，这样会更简单、更高效。给定一个数组 words，创建一个单词映射：

var freq = words.reduce(function(p, c) {
    p[c] = (p[c] || 0) + 1;
    return p;
}, {});

并将其转换为您的数组：

var array = Object.keys(freq).map(function(key) {
   return { text: key, size: freq[key] };
});

- Alnitak

Answer 2

Array.prototype.some 函数期望传入的回调函数返回 true 或 false，并在你的回调函数第一次对于给定元素返回 true 时即返回 true，否则返回 false。

因此，some 函数使用给定的回调函数对所有元素进行迭代，你的回调函数检查所给定元素的文本是否等于“搜索词”，如果不等于，则添加一个新对象。这样，some 函数可以迭代新添加的元素。

因此，为了清晰易懂起见，对于在你搜索的单词之前出现的所有单词，都会添加一个包含该单词的新对象。

假设你的 newArray 如下所示： [{word:"test"},{word:"another"},{word:"one"},{word:"more"}] 当你针对单词 even 调用函数后，它将变为： [{word:"test"},{word:"another"},{word:"one"},{word:"more"},{word:"even"},{word:"even"},{word:"even"},{word:"even"}] 使用 Array.prototype.filter 将是更好的方法，在这里找到匹配的元素，注意我还用 Array.prototype.forEach 替换了 $.each:

function wordFrequency(txt){
  var wordArray = txt.split(/[ .?!,*'"]/);
  var newArray = [], wordObj;
  wordArray.forEach(function (word) {
    wordObj = newArray.filter(function (w){
      return w.text == word;
    });
    if (wordObj.length) {
      wordObj[0].size += 1;
    } else {
      newArray.push({text: word, size: 1});
    }
  });
  return newArray;
}
document.write(JSON.stringify(wordFrequency("count everything, count all the words, count all the words!").sort(function(a,b){return a.size<b.size})).split("},").join("}<br/>"));

- LJᛃ

Answer 3

告诉频率只需要使用哈希映射方法。由于some方法嵌套在each方法中，所以您的算法是二次的，因此您总是循环遍历newArray以查找条目并增加大小。

使用JavaScript对象很容易实现映射方法。 它还为您提供了恒定的查找时间，这比嵌套循环的方法具有更好的性能。

请尝试使用以下方法：

function wordFrequency(txt){
    var wordArray = txt.split(/[ .?!,*'"]/);
    var map = {};
    $.each(wordArray, function(ix, word) {
      // skip empty results
      if (!word.length) {
        return;
      }
      // add word to map
      if (!map[word]) {
        map[word] = 0;
      } 
      map[word]++;
    });
    return map;
}

使用该函数：

var text = "hello!world*hello foo  'bar'foo";
var result = wordFrequency(text);

// iterate over results
Object.keys(result).forEach(function(w) {
  console.log(w + ": " + result[w]);
});

// or use for...in
for (var w in result) {
  console.log(w + ": " + result[w]);
}

如果你真的想要的话，你可以将结果映射到所需的数组格式中，包括文本和大小属性：

var mappedResult = Object.keys(result).map(function(w) {
  return { text: w, size: result[w] };
});
console.log(mappedResult);

此外，根据您的目标浏览器，您可能考虑使用数组forEach而不是jQuery $.each，类似于我在Object.keys部分所做的操作。

这里是JSBin示例。

- Ahmad Mageed

---

使用 wordArray.forEach(function(word){}); 可能更好。 - Asher

Answer 4

您可能希望避免在重复元素上进行任何迭代，并保持结果数组的唯一性。由于Array.prototype的任何迭代器都将包含每个元素，因此它们可能不是解决此问题的理想解决方案。有时，最好使用普通的循环来完成任务...（您还可以明确地转义正则表达式中的任何特殊字符）。

function wordFrequency(txt) {
    var words = txt.split(/[ \.\?!,\*'"]+/),
        seen = [];
    for (var i = 0; i < words.length; i++) {
        var w = words[i],
            found = false;
        for (var j = 0; j < seen.length; j++) {
            if (w === seen[j].text) {
                seen[j].size++;
                found = true;
                break;
            }
        }
        if (!found) seen.push( { text: w, size: 1 } );
    }
    return seen;
}

（请注意，内部for循环不会访问第一个单词，因此第一个单词将被推入已查看堆栈，并且内部for循环将从与第一个单词相比较的第二个单词开始。只有我们尚未看到的单词才会添加到已查看堆栈中，使其成为唯一元素的数组。）

这里是使用Array.prototype.forEach()和Array.prototype.indexOf()的等效方法，但是我们必须为后者添加另一个中间结果堆栈。因此，我们将不得不添加另一个迭代来生成最终结果。（使用Array.prototype.findIndex()，我们不必这样做，但这不是标准方法。）

function wordFrequency2(txt) {
    var words = txt.split(/[ \.\?!,\*'"]+/),
        seen = [],
        freq = [];
    // get frequencies
    words.forEach(function (w) {
        var idx = seen.indexOf(w);
        if (idx >= 0) {
            freq[idx]++;
        }
        else {
            seen.push(w);
            freq.push(1);
        }
    });
    // produce the results array
    var r = [];
    seen.forEach(function (w, idx) {
        r.push( { text: w, size: freq[idx] } );
    });
    return r;
}

考虑到优化，使用显式循环的第一个版本可能会执行得更快...

- masswerk

---

@Alnitak 这是假设顺序很重要的情况。由于我们不知道任何用例，因此我们没有权利丢弃这些信息（如果使用关联数组/哈希表，则会出现这种情况）。我猜想这可能是相关的，因为使用对象键可以轻松解决问题。（如果（seen [w]）freq [w] ++;) - masswerk

好的，我现在明白你想做什么了，尽管结果仍然是一个O(n * m)的算法。 - Alnitak

你无法避免这个问题，因为即使是哈希查找（freq[w]）也相当于内部循环。它可能更高效，因为哈希可能在内部有序，但生成哈希键也会有惩罚。对于真正的大文本，我们可以考虑使用B树来存储任何已见过的单词，但我怀疑这不是这种情况的用例。 - masswerk

不，一个好的哈希查找是O(1)而且 不等同于 一个内部循环。在JS中，对象属性查找是高度优化的。 - Alnitak

我真的不认为这是一个问题，因为我怀疑在JS中解决的问题涉及大量的数据。此外，我自己在类似的问题上使用哈希。无论如何，问题中提出的算法保持了单词在文本中出现的初始顺序，并遇到了内存不足的问题。这就是问题所在，而且没有改变初始算法的任何规格。（请注意，对象的内存占用更大，并且需要维护B树。） - masswerk

Answer 5

var words = (function(){

var sWords = document.body.innerText.toLowerCase().trim().replace(/[,;.]/g,'').split(/[\s\/]+/g).sort();
var iWordsCount = sWords.length; // count w/ duplicates

// array of words to ignore
var ignore = ['and','the','to','a','of','for','as','i','with','it','is','on','that','this','can','in','be','has','if'];
ignore = (function(){
var o = {}; // object prop checking > in array checking
var iCount = ignore.length;
for (var i=0;i<iCount;i++){
o[ignore[i]] = true;
}
return o;
}());

var counts = {}; // object for math
for (var i=0; i<iWordsCount; i++) {
var sWord = sWords[i];
if (!ignore[sWord]) {
counts[sWord] = counts[sWord] || 0;
counts[sWord]++;
}
}

var arr = []; // an array of objects to return
for (sWord in counts) {
arr.push({
text: sWord,
frequency: counts[sWord]
});
}

// sort array by descending frequency | https://dev59.com/V2ox5IYBdhLWcg3w_ZV0#8837505
return arr.sort(function(a,b){
return (a.frequency > b.frequency) ? -1 : ((a.frequency < b.frequency) ? 1 : 0);
});

}());

(function(){
var iWordsCount = words.length; // count w/o duplicates
for (var i=0; i<iWordsCount; i++) {
var word = words[i];
console.log(word.frequency, word.text);
}
}());

- Andrew