|
摘要：在Java中，對一個數(shù)組或列表(在本文中統(tǒng)稱為集合)中的元素排序，是一個很經(jīng)常的事情。好在Sun公司在Java庫中實現(xiàn)了大部分功能。如果集
合中的元素實現(xiàn)了Comparable接口，調(diào)用Array或Collections的靜態(tài)(static)方法sort，就可以直接對集合排序。程序員
用不同的方式實現(xiàn)了Comparator接口，就可以用各自不同的方式排序。對于包含漢字的字符串來說，排序的方式主要有兩種：一種是拼音，一種是筆畫。
本文就講述如何實現(xiàn)這兩種不同的比較器(Comparator)。
作者：Jeff
發(fā)表于：2007年12月21日 11:27 最后更新于：
2007年12月21日 12:38
版權(quán)聲明：可以任意轉(zhuǎn)載，轉(zhuǎn)載時請務(wù)必以超鏈接形式標(biāo)明文章
原始出處和作者信息及本版權(quán)聲明。
http://www./jeff-lau/archive/2007/12/21/169257.html
排序概述
在Java中，對一個數(shù)組或列表(在本文中統(tǒng)稱為集合)中的元素排序，是一個很經(jīng)常的事情。好在Sun公司在Java庫中實現(xiàn)了大部分功能。如果集合中的元素實現(xiàn)了Comparable接口，調(diào)用以下的靜態(tài)(static)方法，就可以直接對集合排序。
// 數(shù)組排序方法
// 數(shù)組中的元素可以是像int這樣的原生類型(primitive type),
也可以是像String這樣實現(xiàn)了Comparable接口的類型，這里用type表示。
java.util.Arrays.sort(type[] a);
// 列表
public static <T> void sort(List<T> list)
以上的這些排序方式能滿足大部分應(yīng)用。但集合中的元素沒有實現(xiàn)Comparable接口，或者集合中的元素要按一種特別的方式排序，這要怎么辦？Sun公司早就想到了，并在Java庫中提供上面兩個方法的重載。
// 數(shù)組排序方法。
// 數(shù)組中的元素可以是像int這樣的原生類型(primitive type),
也可以是像String這樣實現(xiàn)了Comparable接口的類型，這里用type表示。
public static <T> void sort(T[] a, Comparator<? super
T> c)
// 列表
public static <T> void sort(List<T> list,
Comparator<? super T> c)
只要實現(xiàn)了Comparator接口，就可以按程序員自己的意思去排序了。對于包含漢字的字符串來說，排序的方式主要有兩種：一種是拼音，一種是筆畫。漢字是通過一定的編碼方式存儲在計算機上的，主要的編碼有：Unicdoe、GB2312和GBK等。
Unicode 編碼中的漢字
Unicode中編碼表分為兩塊，一個是基本的，一個是輔助的?，F(xiàn)在的大多數(shù)操作系統(tǒng)還不支持Unicode中輔助區(qū)域中的文字，如WinXp。
在Java中的字符就是Unicode碼表示的。對于Unicode基本區(qū)域中的文字，用兩個字節(jié)的內(nèi)存存儲，用一個char表示，而輔助區(qū)域中的文字用
4個字節(jié)存儲，因此輔助區(qū)域中的就要用兩個char來表示了(表一種藍(lán)色底就是輔助區(qū)域中的文字)。一個文字的unicode編碼，在Java中統(tǒng)一用
codePoint(代碼點)這個概念。
中文和日文、韓文一樣是表意文字，在Unicode中，中日韓三國(東亞地區(qū))的文字是統(tǒng)一編碼的。CJK代表的就是中日韓。在這里，我把這3中文字，都作為漢字處理了。(日語和韓語可能就是從漢語中衍生的吧！)
漢字在Unicode中的分布大致如下表：
| |
首字編碼 |
尾字編碼 |
個數(shù) |
| 基本漢字 |
U4E00 |
U9FBF |
20928 |
| 異性字 |
UF900 |
UFAFF |
512 |
| 擴展A |
U3400 |
U4D8F |
512 |
| 擴展B |
U20000 |
U2A6DF |
42720 |
| 補充 |
U2F800 |
U2FA1F |
544 |
| 其他 |
|
|
... |
表一
在這些編碼區(qū)間，有些編碼是保留的。
GB2312編碼
GB2312是中華人民共和國最早的計算機漢字編碼方式。大概有6000多個漢字，這些漢字是按拼音順序編碼的。這6000多個漢字都是簡體中文字。
GBK編碼
GB2312的擴展，并兼容GB2312。擴展后的漢字大概有2萬多個，其中有簡體漢字也有繁體漢字。
拼音排序
拼音有好幾種方式，其中最主要的是中華人民共和國的漢語拼音 Chinese
Phonetic。對漢字的排序有兩種：一種是寬松的，能夠按拼音排序最常用的漢字，另一種是嚴(yán)格的，能夠按拼音排序絕大部分大部分漢字。
寬松的拼音排序法
原理：漢字最早是GB2312編碼，收錄了六千多個漢字，是按拼音排序的，編碼是連續(xù)的。
后來出現(xiàn)了GBK編碼，對GB2312進行了擴展，到了兩萬多漢字，并且兼容GB2312，也就是說GB2312中的漢字編碼是原封不動搬到GBK中的(在GBK編碼中[B0-D7]區(qū)中)。
如果我們只關(guān)心這6000多個漢字的順序，就可以用下面的方法實現(xiàn)漢字寬松排序。
/**
* @author Jeff
*
* Copyright (c) 復(fù)制或轉(zhuǎn)載本文，請保留該注釋。
*/
package chinese.utility;
import java.text.Collator;
import java.util.Comparator;
import java.util.Locale;
public class PinyinSimpleComparator implements
Comparator<String> {
public int compare(String o1, String o2) {
return
Collator.getInstance(Locale.CHINESE).compare(o1, o2);
}
}
在對[孫, 孟, 宋, 尹, 廖, 張, 徐, 昆, 曹, 曾,怡]這幾個漢字排序，結(jié)果是：[曹, 昆, 廖, 孟, 宋, 孫,
徐, 尹, 曾, 張, 怡]。最后一個 怡 有問題，不該排在最后的。
注意：這個程序有兩個不足
-
由于gb2312中的漢字編碼是連續(xù)的，因此新增加的漢字不可能再按照拼音順序插入到已有的gb2312編碼中，所以新增加的漢字不是按拼音順序排的。
- 同音字比較的結(jié)果不等于0 。
下面的測試代碼可以證明
/**
* @author Jeff
*
* Copyright (c) 復(fù)制或轉(zhuǎn)載本文，請保留該注釋。
*/
/**
* 非常用字(怡)
*/
@Test
public void testNoneCommon() {
Assert.assertTrue(comparator.compare("怡", "張")
> 0);
}
/**
* 同音字
*/
@Test
public void testSameSound() {
Assert.assertTrue(comparator.compare("怕", "帕")
!= 0);
}
嚴(yán)格的拼音排序法
為了解決寬松的拼音的兩點不足，可以通過實現(xiàn)漢語拼音的函數(shù)來解決。goolge下看到sf上有個pinyin4j的項目，可以解決這個問題，pinyin4j的項目地址是：http://pinyin4j./。
實現(xiàn)代碼：
/**
* @author Jeff
*
* Copyright (c) 復(fù)制或轉(zhuǎn)載本文，請保留該注釋。
*/
package chinese.utility;
import java.util.Comparator;
import net.sourceforge.pinyin4j.PinyinHelper;
public class PinyinComparator implements
Comparator<String> {
public int compare(String o1, String o2)
{
for (int i = 0; i
< o1.length() && i < o2.length(); i++) {
int codePoint1 = o1.charAt(i);
int codePoint2 = o2.charAt(i);
if (Character.isSupplementaryCodePoint(codePoint1)
|| Character.isSupplementaryCodePoint(codePoint2)) {
i++;
}
if (codePoint1 != codePoint2) {
if (Character.isSupplementaryCodePoint(codePoint1)
|| Character.isSupplementaryCodePoint(codePoint2)) {
return codePoint1 - codePoint2;
}
String pinyin1 = pinyin((char) codePoint1);
String pinyin2 = pinyin((char) codePoint2);
if (pinyin1 != null && pinyin2 != null) { // 兩個字符都是漢字
if (!pinyin1.equals(pinyin2)) {
return pinyin1.compareTo(pinyin2);
}
} else {
return codePoint1 - codePoint2;
}
}
}
return o1.length() -
o2.length();
}
/**
* 字符的拼音，多音字就得到第一個拼音。不是漢字，就return
null。
*/
private String pinyin(char c) {
String[] pinyins =
PinyinHelper.toHanyuPinyinStringArray(c);
if (pinyins == null)
{
return null;
}
return pinyins[0];
}
}
測試：
/**
* @author Jeff
*
* Copyright (c) 復(fù)制或轉(zhuǎn)載本文，請保留該注釋。
*/
package chinese.utility.test;
import java.util.Comparator;
import org.junit.Assert;
import org.junit.Test;
import chinese.utility.PinyinComparator;
public class PinyinComparatorTest {
private Comparator<String> comparator =
new PinyinComparator();
/**
* 常用字
*/
@Test
public void testCommon() {
Assert.assertTrue(comparator.compare("孟", "宋")
< 0);
}
/**
* 不同長度
*/
@Test
public void testDifferentLength() {
Assert.assertTrue(comparator.compare("他奶奶的",
"他奶奶的熊") < 0);
}
/**
* 和非漢字比較
*/
@Test
public void testNoneChinese() {
Assert.assertTrue(comparator.compare("a", "阿")
< 0);
Assert.assertTrue(comparator.compare("1", "阿")
< 0);
}
/**
* 非常用字(怡)
*/
@Test
public void testNoneCommon() {
Assert.assertTrue(comparator.compare("怡", "張")
< 0);
}
/**
* 同音字
*/
@Test
public void testSameSound() {
Assert.assertTrue(comparator.compare("怕", "帕")
== 0);
}
/**
* 多音字(曾)
*/
@Test
public void testMultiSound() {
Assert.assertTrue(comparator.compare("曾經(jīng)",
"曾迪") > 0);
}
}
我的這樣嚴(yán)格的拼音排序還是有有待改進的地方，看上面測試代碼的最后一個測試，就會發(fā)現(xiàn)：程序不會根據(jù)語境來判斷多音字的拼音，僅僅是簡單的取多音字的第一個拼音。
筆畫排序
要按筆畫排序，就要實現(xiàn)筆畫比較器。
class StokeComparator implements
Comparator<String>
如果有個方法可以求得漢字的筆畫數(shù)，上面的功能就很容易實現(xiàn)。如何求一個漢字的筆畫數(shù)？最容易想到的就是查表法。建一個漢字筆畫數(shù)表，如：
| 漢字 |
Unicode編碼 |
筆畫數(shù) |
| 一 |
U4E00 |
1 |
| 二 |
U4E8C |
2 |
| 龍 |
U9F8D |
16 |
| ... |
... |
... |
表二
如果是連續(xù)的、按unicode編碼排好順序的表，實際存儲在筆畫數(shù)表中的只需最后一列就夠了。
那如何建這個表呢？這個表存儲在哪里？
建漢字筆畫數(shù)表
現(xiàn)在大多數(shù)系統(tǒng)還只能支持Unicode中的基本漢字那部分漢字，編碼從U9FA6-U9FBF。所以我們只建這部分漢字的筆畫表。漢字筆畫數(shù)表，我們可以按照下面的方法生成：
-
用java程序生成一個文本文件(Chinese.csv)。包括所有的從U9FA6-U9FBF的字符的編碼和文字。利用excel的按筆畫排序功能，對Chinese.csv文件中的內(nèi)容排序。
- 編寫Java程序分析Chinese.csv文件，求得筆畫數(shù),
生成ChineseStroke.csv。矯正筆畫數(shù)，重新按漢字的Unicode編碼對ChineseStroke.csv文件排序。
- 只保留ChineseStroke.csv文件的最后一列，生成Stroke.csv。
在這里下載上面3個步驟生成的3個文件。
生成Chinese.csv的Java程序
/**
* @author Jeff
*
* Copyright (c) 復(fù)制或轉(zhuǎn)載本文，請保留該注釋。
*/
package chinese.utility.preface;
import java.io.IOException;
import java.io.PrintWriter;
public class ChineseCoder {
public static void main(String[] args) throws
IOException {
PrintWriter out = new
PrintWriter("Chinese.csv");
// 基本漢字
for(char c = 0x4E00; c
<= 0x9FA5; c++) {
out.println((int)c + "," + c);
}
out.flush();
out.close();
}
}
初始化筆畫數(shù)
從Excel排序過后的Chinese.csv文件來看，排好序的文件還是有一定規(guī)律的。在文件的第9行-12行可以看出：逐行掃描的時候，當(dāng)unicode會變小了，筆畫數(shù)也就加1。
20059,乛
20101,亅
19969,丁
19970,丂
用下面的Java程序分析吧。
/**
* @author Jeff
*
* Copyright (c) 復(fù)制或轉(zhuǎn)載本文，請保留該注釋。
*/
package chinese.utility.preface;
import java.io.File;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Scanner;
public class Stroke {
/**
* @param args
* @throws IOException
*/
public static void main(String[] args) throws
IOException {
Scanner in = new
Scanner(new
File("Chinese.csv"));
PrintWriter out = new
PrintWriter("ChineseStroke.csv");
String oldLine =
"999999";
int stroke = 0;
while (in.hasNextLine())
{
String line = in.nextLine();
if (line.compareTo(oldLine) < 0) {
stroke++;
}
oldLine = line;
out.println(line + "," +
stroke);
}
out.flush();
out.close();
in.close();
}
}
上面用的這個規(guī)律有問題嗎？有問題，從ChineseStroke.csv文件抽取最后幾個漢字就發(fā)現(xiàn)，筆畫數(shù)不對。為什么呢？
- 筆畫數(shù)可能不是連續(xù)的。
- n+1筆畫數(shù)的最小Unicode碼可能比n筆畫數(shù)的最大Unicode碼要大
我們要人工核對ChineseStroke文件，但只要核對在筆畫變化的那幾個漢字的筆畫數(shù)。最后，我發(fā)現(xiàn)，只有筆畫數(shù)多于30的少數(shù)幾個漢字的筆畫數(shù)不
對。核對并矯正筆畫數(shù)后，用Excel按Unicode重新排序，去掉漢字和Unicode兩列，只保留筆畫數(shù)那列，得到Stroke.csv文件。
求得筆畫數(shù)的方法和筆畫比較器方法
求得筆畫數(shù)的方法測試代碼：
/**
* @author Jeff
*
* Copyright (c) 復(fù)制或轉(zhuǎn)載本文，請保留該注釋。
*/
package chinese.utility.test;
import static org.junit.Assert.assertEquals;
import org.junit.Before;
import org.junit.Test;
import chinese.utility.Chinese;
public class StrokeTest {
Chinese chinese;
@Before
public void setUp() {
chinese = new
Chinese();
}
@Test
public void testStroke() {
assertEquals(1,
chinese.stroke(‘一‘));
}
@Test
public void testStroke2() {
assertEquals(2,
chinese.stroke(‘二‘));
}
@Test
public void testStroke16() {
assertEquals(16,
chinese.stroke(‘龍‘));
}
@Test
public void testStrokeABC() {
assertEquals(-1,
chinese.stroke(‘a(chǎn)‘));
}
}
求得筆畫數(shù)的方法代碼
/**
* @author Jeff
*
* Copyright (c) 復(fù)制或轉(zhuǎn)載本文，請保留該注釋。
*/
package chinese.utility;
import java.util.Comparator;
public class StrokeComparator implements
Comparator<String> {
public int compare(String o1, String o2)
{
Chinese chinese = new
Chinese();
for (int i = 0; i
< o1.length() && i < o2.length(); i++) {
int codePoint1 = o1.codePointAt(i);
int codePoint2 = o2.codePointAt(i);
if (codePoint1 == codePoint2)
continue;
int stroke1 = chinese.stroke(codePoint1);
int stroke2 = chinese.stroke(codePoint2);
if (stroke1 < 0 || stroke2 < 0) {
return codePoint1 - codePoint2;
}
if (stroke1 != stroke2) {
return stroke1 - stroke2;
}
}
return o1.length() -
o2.length();
}
}
筆畫比較器測試
/**
* @author Jeff
*
* Copyright (c) 復(fù)制或轉(zhuǎn)載本文，請保留該注釋。
*/
package chinese.utility.test;
import java.util.Comparator;
import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;
import chinese.utility.StrokeComparator;
public class StrokeComparatorTest {
private Comparator<String>
comparator;
@Before
public void setUp() {
comparator = new
StrokeComparator();
}
/**
* 相同筆畫數(shù)
*/
@Test
public void testCompareEquals() {
Assert.assertTrue(comparator.compare("一", "丨")
== 0);
}
/**
* 不同筆畫數(shù)
*/
@Test
public void testCompare() {
Assert.assertTrue(comparator.compare("一", "二")
< 0);
Assert.assertTrue(comparator.compare("唔", "馬")
> 0);
}
/**
* 長度不同
*/
@Test
public void testCompareDefficultLength() {
Assert.assertTrue(comparator.compare("二", "二一")
< 0);
}
/**
* 非漢字的比較
*/
@Test
public void testABC() {
Assert.assertTrue(comparator.compare("一", "a")
> 0);
Assert.assertTrue(comparator.compare("a", "b")
< 0);
}
}
筆畫比較器
/**
* @author Jeff
*
* Copyright (c) 復(fù)制或轉(zhuǎn)載本文，請保留該注釋。
*/
package chinese.utility.test;
import java.util.Comparator;
import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;
import chinese.utility.StrokeComparator;
public class StrokeComparatorTest {
private Comparator<String>
comparator;
@Before
public void setUp() {
comparator = new
StrokeComparator();
}
/**
* 相同筆畫數(shù)
*/
@Test
public void testCompareEquals() {
Assert.assertTrue(comparator.compare("一", "丨")
== 0);
}
/**
* 不同筆畫數(shù)
*/
@Test
public void testCompare() {
Assert.assertTrue(comparator.compare("一", "二")
< 0);
Assert.assertTrue(comparator.compare("唔", "馬")
> 0);
}
/**
* 長度不同
*/
@Test
public void testCompareDefficultLength() {
Assert.assertTrue(comparator.compare("二", "二一")
< 0);
}
/**
* 非漢字的比較
*/
@Test
public void testABC() {
Assert.assertTrue(comparator.compare("一", "a")
> 0);
Assert.assertTrue(comparator.compare("a", "b")
< 0);
}
}
其他程序的漢字排序
Microsoft在這方面做得比較好。如Sql server
2000，Word和Excel都能按拼音和筆畫排序。而Oracle只能是采取寬松拼音排序法。
|
