用JavaScript截取字符串左边长度为n的子串

2010-08-19

我们经常需要用 JavaScript 取得一个字条串的左边长度为 n 的子串(比如用于显示标题、摘要等),大多数情况下,直接用 substring 等原生方法就可以,但这些方法把汉字和英文字母的长度都算作 1 ,而有时为了排版需要,我们需要把汉字等全角字符的长度算作 2 ,这时就只能自己实现方法了。

首先我们需要做的是判断哪些字符是半角,哪些是全角,还好,用正则能比较方便地判断,比如:

function foo(c) {
	alert("字符 '" + c + "' 是 " + (c.match(/[x00-xff]/g) ? "半角" : "全角"));
}
var c1 = "a", c2 = "中";
foo(c1);
foo(c2);

如果给定一个字符串 s ,最容易想到的办法大概是从左到右一个字符一个字符地扫描,每次判断一下当前字符是半角还是全角,如果是半角,则长度加 1 ,如果是全角,则长度加 2 ,直到长度达到 n 。比如:

// 方法一
// 从左边截取n个字符,如果包含汉字,则汉字按两个字符计算
function test_1(s, n) {
	var l = 0, i = 0, c;
	while (l < n) {
		c = s.substr(i, 1);
		if (c.match(/[x00-xff]/g)) // 或计算 charCodeAt,看是否在 0~255 内
			l ++;
		else
			l += 2;
	}
	return s.substr(0, l);
}

这个函数基本上可以工作,但是效率上却有那么点低,因为要取多少个字符,就要循环多少次、做多少次正则判断,而且当 n 远大于 s 的长度时,它也不会适时地跳出循环。

注意到我们要取的字串一定是包含在 s.substr(0, n) 中的,我们可以换一种思路,先取出 s.substr(0, n) ,再计算它的长度(汉字长度算 2 ),如果这个长度大于 n 则抛掉最右边的那个字符,重复这个过程直到长度小于等于 n 。即:

function lenB(s) {
	// 返回一个字符串的长度,ASCII 字符长度为1,其它字符长度算2
	return s.replace(/[^x00-xff]/g, "**").length;
}

// 方法二
// 从左边截取n个字符,如果包含汉字,则汉字按两个字符计算
function test_2(s, n) {
	var s = s.slice(0, n);
	while (lenB(s) > n) {
		s = s.slice(0, s.length - 1);
	}
	return s;
}

这个在 s 的总长与 n 都比较小时性能已经好多了,但是如果 s.length 、 n 都很大时,效率上就会存在比较大的瓶颈。比如,在一篇混杂着全角与半角的 10000 字的帖子中取左边长度为 5000 的子串,第一步取出来的 5000 个字符中可能有一小半都要去掉,这个循环的量还是比较大的。

基本上,常见的方法主要就这两种,一种是从头开妈扫描,另一种是先取出 n 个字符,再把尾部超出的部分去掉。当然,上面两种写法在效率上都还可以再进行优化。不过除此之外,我也想到另外一种不同的方法。

第一步,和第二种方法一样,也是先取出 s.slice(0, n) ,接下来,算一下这个小字符串中全角字符有多少个,比如说有 i 个,那就再在这个小字符串中取前 n' - i 个字符(n' 为小字符串的长度)。当然,具体处理上还有一些细节,简单来说,如下图所示:

js 取得字符串左边长度为 n 的子串

代码如下:

// 方法三,我原创的方法
// 从左边截取n个字符,如果包含汉字,则汉字按两个字符计算
function strLeft(s, n) {
	var s2 = s.slice(0, n),
		i = s2.replace(/[x00-xff]/g, "").length;
	switch (i) {
		case 0: return s2;
		case n: return s.slice(0, n>>1);
		default:
			var k = n - i,
				s3 = s.slice(k, n),
				j = s3.replace(/[x00-xff]/g, "").length;
			return j ? s.slice(0, k) + strLeft(s3, j) : s.slice(0, k);
	}
}

前两种算法的时间复杂度都是 O(n) ,这个算法的时间复杂度为 O(log(n))。与前两个方法相比,在输入的 s 及 n 规模都较小时效率差不多或稍快一些,不过在处理超长字符串时(比如在长度为 10000 的包含中英文的字符串中截取左边长度为 5000 的子串)它非常快,经我在 Firefox 和 IE 上的测试,基本上可以比前两个方法快出一个数量级甚至更多。

另外,还有一个不大不小的问题,即当 n 比 s.length 大出很多时,其实第一步 s.slice(0, n) 就已经是最终结果了,但上面的代码中没有做判断,还会再继续判断中间有多少双字节字符,在这种情况下会有一定的性能损失。经过综合考虑之后,上面的代码还能再优化为:

// 方法三的最终形式
// 从左边截取n个字符,如果包含汉字,则汉字按两个字符计算
function strLeft(s, n) {
	var s2 = s.slice(0, n),
		i = s2.replace(/[^x00-xff]/g, "**").length;
	if (i <= n) return s2;
	i -= s2.length;
	switch (i) {
		case 0: return s2;
		case n: return s.slice(0, n>>1);
		default:
			var k = n - i,
				s3 = s.slice(k, n),
				j = s3.replace(/[x00-xff]/g, "").length;
			return j ? s.slice(0, k) + strLeft(s3, j) : s.slice(0, k);
	}
}

这样,这段代码基本上在所有情况下都能表现良好了。

关于截取字符串的效率目前就探索到这里了,不过实际应用中,还会遇到一些具体的需求问题,主要是半个字符的处理。比如,如果要求截取字符串 123汉字 左边长度为 4 的子串,应该返回什么呢?返回 123 还是 123汉?一般的处理是返回 123,我上面的方法三也是返回 123,但如果万一遇到变态的需求方,那就得改动代码特殊处理了。


PS:

网上流传着一种看似非常简单的方法,代码如下:

function wrongFunc(s, n) {
 return s.slice(0, n - s.slice(0, n).replace(/[x00-xff]/g, "").length);
}

我没有找到这个方法的原始出处,它看似很简单很酷,但实际上是错误的。比如,求汉字123测试456的左边长度为7的子串,按理应该返回汉字123,但它会返回汉字1,原因是它多减去了后面的测试两个字符的长度。

PS 2:

在网上看到另一种非常简单的方法,代码如下:

function func(s, n) {
 return s.replace(/([^x00-xff])/g, "$1a").slice(0, n).replace(/([^x00-xff])a/g, "$1");
}

这个方法非常巧妙,而且基本上是正确的。说“基本上”是因为它在取123汉字测试左边长度为 6 的子串时,它返回的是123汉字,而不是123汉。当然,这也并不一定就是问题,某些情况下需求可能就是这样。这个方法还可以再改进一下,如下:

function func(s, n) {
 return s.slice(0, n).replace(/([^x00-xff])/g, "$1a").slice(0, n).replace(/([^x00-xff])a/g, "$1");
}

不过即使这个改进后的版本,还是比上面我提出的方法三的效率要低,因为它虽然写法简单,但有时也会多做一些不必要的计算。

知识共享许可协议
本作品采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。
分类: 编程 标签: JavaScript 算法
前一篇: 使用Cocos2d模拟N体问题
后一篇: 关于星期二男孩问题的进一步思考

相关文章:

评论:

Kenny Yuan
在 2010-09-06 15:52 写道:

logN似乎不对吧?用到的内建功能(如replace)也还是需要遍历的吧?

回复
oldj
在 2010-09-06 15:52 写道:

嗯,只考虑循环/递归的规模大致是 logN ,内建功能(如 replace、slice)三种方法都要用到,而且内建功能效率远高于外部代码,所以没有考虑到时间复杂度上来。:-)

回复
ear
在 2011-10-29 07:08 写道:

这段代码怎么样function correctFunc(str, n) { var en=0,zh=0 if(str.length<n){n=str.length;} for(var i=0;i<n;i++) { if( str.substr(i,1).match(/[x00-xff]/g) ){en++;} else{zh++;} if (en+2*zh>n){return str.substr(0,i);} } return str.substr(0,n);  }

回复
oldj
在 2011-10-29 07:08 写道:

你这段代码似乎就是方法一的代码,从左往右逐字验证。这种方法,在 str.length 或 n 比较小时没问题,但当两者很大(比如 5000+)时,这个循环会执行 Min(str.length, n) 次,每一次都要执行正则匹配,这种情况下效率还是有点低的。

回复
ear
在 2011-10-29 15:55 写道:

js还是没有c自由啊

回复
ear
在 2011-10-29 18:38 写道:

(c<="xff") ? "半角" : "全角")); 这样是不是比原先要快?

回复
oldj
在 2011-10-29 18:38 写道:

看起来应该是这样更快一些,但我做了一个简单的测试(http://jsperf.com/reg-vs-str-comp),两者好像性能相差不大...

回复

发表评论:

电子邮件地址不会被公开。 必填项已用 * 标注。