fastscan - npm Package Compare versions

Comparing version 1.0.4 to 1.0.5

index.bench.js

+var FastScanner = require('./index')
+var chars = 'abcdefghijklmnopqrstuv'
+
+function randomString(min, max) {
+	var cs = []
+	var len = 0
+	if(min == max) {
+		len = min
+	} else {
+		len = Math.floor(Math.random() * (max-min)) + min
+	}
+	for(var i=0;i<len;i++) {
+		var k = Math.floor(Math.random() * chars.length)
+		cs.push(chars[k])
+	}
+	return cs.join('')
+}
+
+function randomWords(wordNum, min, max) {
+	var words = []
+	for(var k=0;k<wordNum;k++) {
+		words.push(randomString(min, max))
+	}
+	return words
+}
+
+function benchBuild() {
+	var wordLen = [10, 20]
+	var wordNums = [20000, 40000, 60000, 80000, 100000]
+	for(var i=0;i<wordNums.length;i++) {
+		var words = randomWords(wordNums[i], wordLen[0], wordLen[1])
+		var start = new Date().getTime()
+		var scanner = new FastScanner(words)
+		var end = new Date().getTime()
+		console.log("build ac tree of %d words costs %dms", words.length, end - start)
+	}
+}
+
+function benchSearch() {
+	var wordLen = [10, 20]
+	var wordNums = [20000, 40000, 60000, 80000, 100000]
+	var articleLens = [20000, 40000, 60000, 80000, 100000]
+	var articles = []
+	for(var i=0;i<articleLens.length;i++) {
+		articles.push(randomString(articleLens[i], articleLens[i]))
+	}
+	for(var i=0;i<wordNums.length;i++) {
+		var words = randomWords(wordNums[i], wordLen[0], wordLen[1])
+		var scanner = new FastScanner(words)
+		for(var k=0;k<articles.length;k++) {
+			var start = new Date().getTime()
+			scanner.search(articles[k])
+			var end = new Date().getTime()
+			console.log("search article of %d chars by %s words tree costs %dms", articles[k].length, wordNums[i], end - start)
+		}
+	}
+}
+
+function benchMemory() {
+	var wordLen = [10, 20]
+	var wordNums = [0, 20000, 40000, 60000, 80000, 100000]
+	for(var i=0;i<wordNums.length;i++) {
+		var words = randomWords(wordNums[i], wordLen[0], wordLen[1])
+		gc()
+		var before = process.memoryUsage()
+		var scanner = new FastScanner(words)
+		gc()
+		var after = process.memoryUsage()
+		scanner.search('abcdefg')
+		console.log("build tree of %d words costs rss=%dM heapTotal=%dM heapUsed=%dM", wordNums[i], (after.rss-before.rss) >> 20, (after.heapTotal - before.heapTotal) >> 20, (after.heapUsed - before.heapUsed) >> 20)
+	}
+}
+
+benchBuild()
+benchSearch()
+benchMemory()

index.js

@@ -14,3 +14,3 @@ (function () {
 			val: null, // 当前节点的字符，null表示根节点
-			back: null, // 回溯指针，也称失败指针
+			back: null, // 跳跃指针，也称失败指针
 			parent: null, // 父节点指针,
@@ -81,11 +81,11 @@ depth: 0, // 节点深度
 				var back = parent.back
-				// 第一层节点也谈不上回溯
-				if (back == null) {
-					continue;
+				while(back != null) {
+					// 匹配父节点的跳跃节点的子节点
+					var child = back.next[node.val]
+					if (child) {
+						node.back = child
+						break
+					} 
+					back = back.back
 				}
-				// 匹配父节点的回溯节点的子节点
-				var child = back.next[node.val]
-				if (child) {
-					node.back = child
-				}
 			}
@@ -102,12 +102,11 @@ curExpands = nextExpands
 			var back = parent.back
-			// 第一层节点也谈不上回溯
-			if (back == null) {
-				current = current.next[c]
-				continue;
+			while (back != null) {
+				// 匹配父节点的跳跃节点的子节点
+				var child = back.next[current.val]
+				if (child) {
+					current.back = child
+					break
+				}
+				back = back.back
 			}
-			// 匹配父节点的回溯节点的子节点
-			var child = back.next[current.val]
-			if (child) {
-				current.back = child
-			}
 			current = current.next[c]
@@ -142,4 +141,2 @@ }
 		addWord(this.root, word)
-		// var util = require('util')
-		// console.log(util.inspect(this.root, null, 8))
 		fallback(this.root, word)
@@ -186,12 +183,30 @@ }
 		options = options || {}
-		for (var i = 0; i < content.length;) {
+		for (var i = 0; i < content.length;i++) {
 			var c = content[i];
 			var next = current.next[c];
-			if (next) {
+			if(!next) {
+				// 递归匹配跳跃节点的子节点
+				var back = current.back
+				while(back != null) {
+					if(back.accept) {
+						var word = collect(back)
+						offWords.push([i - word.length, word]);
+						// 只选第一个词
+						if (options.quick) {
+							return offWords
+						}
+					}
+					next = back.next[c]
+					if(next) {
+						break
+					}
+					back = back.back
+				}
+			}
+			if(next) {
 				current = next;
-				i++;
 				// 收集匹配的词汇
-				if (next.accept) {
+				if (current.accept) {
 					var word = collect(current)
-					offWords.push([i - word.length, word]);
+					offWords.push([i - word.length + 1, word]);
 					// 只选第一个词
@@ -202,22 +217,6 @@ if (options.quick) {
 				}
-				continue;
+				continue
 			}
-			var back = current.back;
-			if (back == null) {
-				i++;
-				continue;
-			}
-			// 回溯
-			var delta = current.depth - back.depth - 1;
-			current = back;
-			i -= delta;
-			// 收集匹配的词汇
-			if (current.accept) {
-				var word = collect(current)
-				offWords.push([i - word.length, word]);
-				// 只选第一个词
-				if (options.quick) {
-					return offWords
-				}
-			}
+			// 重置
+			current = this.root
 		}
@@ -224,0 +223,0 @@ // 同一个位置选最长的

index.min.js

@@ -1,1 +0,1 @@
-!function(){"use strict";function t(t){this.root=function(t){t=function(t){t=(t=t.map(function(t){return t.trim()})).filter(function(t){return t.length>0});for(var n={},e=[],r=0;r<t.length;r++){var o=t[r];n[o]||(n[o]=!0,e[e.length]=o)}return e.sort()}(t);for(var e={next:{},val:null,back:null,parent:null,depth:0,accept:!1},r=0;r<t.length;r++)n(e,t[r]);return function(t){for(var n=Object.values(t.next);n.length>0;){for(var e=[],r=0;r<n.length;r++){var o=n[r];for(var a in o.next)e.push(o.next[a]);var u=o.parent,i=u.back;if(null!=i){var f=i.next[o.val];f&&(o.back=f)}}n=e}}(e),e}(t)}function n(t,n){for(var e=t,r=0;r<n.length;r++){var o=n[r];e.next[o]||(e.next[o]={next:{},val:o,accept:!1,back:t,parent:e,depth:e.depth+1}),e=e.next[o]}e.accept=!0}function e(t){for(var n=[];null!=t.val;)n.unshift(t.val),t=t.parent;return n.join("")}t.prototype.add=function(t){0!=(t=t.trim()).length&&(n(this.root,t),function(t,n){for(var e=t.next[n[0]],r=1;r<n.length;r++){var o=n[r],a=e.parent.back;if(null!=a){var u=a.next[e.val];u&&(e.back=u),e=e.next[o]}else e=e.next[o]}}(this.root,t))},t.prototype.locate=function(t){for(var n=this.root.next[t[0]],e=1;e<t.length;e++){var r=t[e];if(null==(n=n.next[r]))break}return n},t.prototype.hits=function(t,n){for(var e=this.search(t,n),r={},o=0;o<e.length;o++){var a=e[o][1],u=r[a]||0;r[a]=u+1}return r},t.prototype.search=function(t,n){var r=[],o=this.root;n=n||{};for(var a=0;a<t.length;){var u=t[a],i=o.next[u];if(i){if(o=i,a++,i.accept){var f=e(o);if(r.push([a-f.length,f]),n.quick)return r}}else{var l=o.back;if(null!=l){if(a-=o.depth-l.depth-1,(o=l).accept){f=e(o);if(r.push([a-f.length,f]),n.quick)return r}}else a++}}return n.longest?function(t){for(var n={},e=0;e<t.length;e++){var r=t[e],o=n[r[0]];(!o||o.length<r[1].length)&&(n[r[0]]=r[1])}return Object.keys(n).map(function(t){return parseInt(t)}).sort(function(t,n){return t-n}).map(function(t){return[t,n[t]]})}(r):r},"undefined"!=typeof module&&void 0!==module.exports?module.exports=t:"function"==typeof define&&define.amd?define([],function(){return t}):window.FastScanner=t}();
+!function(){"use strict";function t(t){this.root=function(t){t=function(t){t=(t=t.map(function(t){return t.trim()})).filter(function(t){return t.length>0});for(var n={},r=[],e=0;e<t.length;e++){var o=t[e];n[o]||(n[o]=!0,r[r.length]=o)}return r.sort()}(t);for(var r={next:{},val:null,back:null,parent:null,depth:0,accept:!1},e=0;e<t.length;e++)n(r,t[e]);return function(t){for(var n=Object.values(t.next);n.length>0;){for(var r=[],e=0;e<n.length;e++){var o=n[e];for(var a in o.next)r.push(o.next[a]);for(var u=o.parent,f=u.back;null!=f;){var i=f.next[o.val];if(i){o.back=i;break}f=f.back}}n=r}}(r),r}(t)}function n(t,n){for(var r=t,e=0;e<n.length;e++){var o=n[e];r.next[o]||(r.next[o]={next:{},val:o,accept:!1,back:t,parent:r,depth:r.depth+1}),r=r.next[o]}r.accept=!0}function r(t){for(var n=[];null!=t.val;)n.unshift(t.val),t=t.parent;return n.join("")}t.prototype.add=function(t){0!=(t=t.trim()).length&&(n(this.root,t),function(t,n){for(var r=t.next[n[0]],e=1;e<n.length;e++){for(var o=n[e],a=r.parent.back;null!=a;){var u=a.next[r.val];if(u){r.back=u;break}a=a.back}r=r.next[o]}}(this.root,t))},t.prototype.locate=function(t){for(var n=this.root.next[t[0]],r=1;r<t.length;r++){var e=t[r];if(null==(n=n.next[e]))break}return n},t.prototype.hits=function(t,n){for(var r=this.search(t,n),e={},o=0;o<r.length;o++){var a=r[o][1],u=e[a]||0;e[a]=u+1}return e},t.prototype.search=function(t,n){var e=[],o=this.root;n=n||{};for(var a=0;a<t.length;a++){var u=t[a],f=o.next[u];if(!f)for(var i=o.back;null!=i;){if(i.accept){var c=r(i);if(e.push([a-c.length,c]),n.quick)return e}if(f=i.next[u])break;i=i.back}if(f){if((o=f).accept){c=r(o);if(e.push([a-c.length+1,c]),n.quick)return e}}else o=this.root}return n.longest?function(t){for(var n={},r=0;r<t.length;r++){var e=t[r],o=n[e[0]];(!o||o.length<e[1].length)&&(n[e[0]]=e[1])}return Object.keys(n).map(function(t){return parseInt(t)}).sort(function(t,n){return t-n}).map(function(t){return[t,n[t]]})}(e):e},"undefined"!=typeof module&&void 0!==module.exports?module.exports=t:"function"==typeof define&&define.amd?define([],function(){return t}):window.FastScanner=t}();

index.test.js

@@ -51,2 +51,3 @@ var assert = require('assert');
         var offWords = scanner.search(content)
+		console.log(offWords)
         assert.deepEqual([[1, '近平']], offWords)
@@ -58,7 +59,7 @@ });
         var offWords = scanner.search(content)
-        assert.deepEqual([[3, '习近平'], [3, '习近平好'], [4, '近平'], [11, '习近平'], [12, '近平']], offWords)
+        assert.deepEqual([[3, '习近平'], [3, '习近平好'], [11, '习近平'], [12, '近平']], offWords)
         var offWords = scanner.search(content, { quick: true })
         assert.deepEqual([[3, '习近平']], offWords)
         var offWords = scanner.search(content, { longest: true })
-        assert.deepEqual([[3, '习近平好'], [4, '近平'], [11, '习近平'], [12, '近平']], offWords)
+        assert.deepEqual([[3, '习近平好'], [11, '习近平'], [12, '近平']], offWords)
     });
@@ -65,0 +66,0 @@ });

package.json

 {
   "name": "fastscan",
-  "version": "1.0.4",
+  "version": "1.0.5",
   "description": "quickly search by ahocorasick algorithm ",
   "main": "index.min.js",
   "scripts": {
-    "test": "mocha index.test.js"
+    "test": "mocha index.test.js",
+    "bench": "node --expose-gc index.bench.js"
   },
@@ -9,0 +10,0 @@ "repository": {

README.md

@@ -13,4 +13,2 @@ ## FastScan
 npm install --save fastscan
-# 运行单元测试
-npm test
 ```
@@ -61,3 +59,3 @@
 
-查询性能我并不担心，因为 ahocorasick 算法在词汇长度较短的情况下复杂度是 O(n)，性能和被过滤内容的长度乘线性变化。下面我使用 100000 词汇量构建的树分别对 20000 ～ 100000字的内容进行了过滤，耗时情况如下
+查询性能我并不担心，因为 ahocorasick 算法在词汇长度较短的情况下复杂度是 O(n)，性能和被过滤内容的长度呈线性变化。下面我使用 100000 词汇量构建的树分别对 20000 ～ 100000字的内容进行了过滤，耗时情况如下
 
@@ -64,0 +62,0 @@ 字数|耗时

No alert changes

Improved metrics

Total package byte prevSize

94962

2.32%

Number of package files

9

12.5%

Lines of code

440

18.92%

Worsened metrics

Number of lines in readme file

86

-2.27%

No dependency changes