生成等宽字距字符串的算法
2013年05月05日


我们知道,在很多字体下面,每个英文字母的宽度是不一样的,就拿WI来讲,W的字体宽度要大于I的字体宽度,所以有时候我们会不太喜欢这样的定义。


以下我以Windows下默认的文件名称为例,我对比发现,等宽字符可以分成下面5组:

private static final char [] charsA = new char[]{'V','R','C','K','X'};

private static final char [] charsD = new char[]{'D','G','H','U','A'};

private static final char [] charsN = new char[]{'N','O','Q'};

private static final char [] charsF = new char[]{'E','F','L'};

private static final char [] charsE = new char[]{'B','P','S','T','Y','Z'};

每一组字符时等宽的,我们要想他们组合起来的字符串也是等宽的,那也有很多种情况,不过方法都是类似的,我以5个字母的字符串为例。


就是每个数组各取一个字符,例如各取第一个字符和各取第二个字符,分别是ADNFE和BGOLP,这两个字符串是等宽的


下面给出Java语言版的算法,

private static final char [] charsA = new char[]{'V','R','C','K','X'};
private static final char [] charsD = new char[]{'D','G','H','U','A'};
private static final char [] charsN = new char[]{'N','O','Q'};
private static final char [] charsF = new char[]{'E','F','L'};
private static final char [] charsE = new char[]{'B','P','S','T','Y','Z'};
 
public static String getRandomStr(){
    StringBuffer strbuf = new StringBuffer();
     
    int resultArray[] = { 1, 2, 3, 4, 5 };
    shuffle(resultArray);
    int i = 0;
    for(int j=0;j<resultArray.length;j++){
        switch(resultArray[j]){
            case 1:{
                i = (int) (Math.random()*charsA.length);
                strbuf.append(charsA[i]);
                break;
            }
            case 2:{
                i = (int) (Math.random()*charsD.length);
                strbuf.append(charsD[i]);
                break;
            }
            case 3:{
                i = (int) (Math.random()*charsN.length);
                strbuf.append(charsN[i]);
                break;
            }
            case 4:{
                i = (int) (Math.random()*charsF.length);
                strbuf.append(charsF[i]);
                break;
            }
            case 5:{
                i = (int) (Math.random()*charsE.length);
                strbuf.append(charsE[i]);
                break;
            }
        }
    }
     
    return strbuf.toString();
}


/**
 * 将原始数组重新随机排序(=洗牌)
 * 
 * @param orgIntArray
 *            例如{ 0, 1, 2, 3, 4, 5, 6, 7 }
 */
public static void shuffle(int[] orgIntArray) {
    int pos, temp;
    Random rand = new Random();
    for (int r = orgIntArray.length - 1; r > 0; r--) {
        // 0 ~ r
        pos = Math.abs(rand.nextInt()) % (r + 1);

        // [pos]已使用,与最后那个未使用的交换
        temp = orgIntArray[pos];
        orgIntArray[pos] = orgIntArray[r];
        orgIntArray[r] = temp;
    }
}


二、一个更好的办法

上面那种方法虽然简单,但是局限性较大,随机力度不够,而且那个分组只是把宽度“差不多”的字符放在一个组,但其实每个组里面的元素并不完全一样宽,极端情况下,每个组都抽到最窄(宽)的元素,那么组成的字符串就会很窄(宽),例如

XAQLT,

VDNEB


一个更好的办法是根据字体的宽度来组合,每个组合的总宽度基本一致就行了。

下面是字母在 微软雅黑 12号字体 下面测量得到的宽度排序和像素宽度  (同时也考虑了其他常用字体)

WWWWWWWWWW

MMMMMMMMMM

NNNNNNNNNN

OOOOOOOOOO

QQQQQQQQQQ

DDDDDDDDDD

HHHHHHHHHH

GGGGGGGGGG

UUUUUUUUUU

AAAAAAAAAA

VVVVVVVVVV

RRRRRRRRRR

CCCCCCCCCC

KKKKKKKKKK

XXXXXXXXXX

BBBBBBBBBB

ZZZZZZZZZZ

PPPPPPPPPP

YYYYYYYYYY

SSSSSSSSSS

TTTTTTTTTT

EEEEEEEEEE

FFFFFFFFFF

LLLLLLLLLL

JJJJJJJJJJ

IIIIIIIIII

结果如下(数字代表像素宽度)

W 200

M 194

'N','O','Q'  159

'D','H','G','U'  148

A V 140

'C','R' 134

'K','X','B' 130

'Z','P','Y','S' 118

'T' 113

'E','F' 108

L  100

J  79

I  56


根据这个统计数据,可以求得长度为6的字符串,其平均宽度总和为793,我们只要随机取出6个字母,使得其总宽度在793左右相差不超过10,那么这样的组合就满足他们的宽度几乎差不多。


等宽大写字母字符串(长度为6)的算法代码如下:

// 26个字母各自的宽度
private static final int[] WEIGHT = new int[] {200, 194, 159, 159, 159, 
    148, 148, 148, 148, 140, 140, 134, 134, 130, 130, 130, 
    118, 118, 118, 118, 113, 108, 108, 100, 79, 56};
// 按宽度分组
private static final char [] chars1 = new char[]{'R','C'};
private static final char [] chars2 = new char[]{'N','O','Q'};
private static final char [] chars3 = new char[]{'D','H','G','U'};
private static final char [] chars4 = new char[]{'A','V'};
private static final char [] chars5 = new char[]{'K','X','B'};
private static final char [] chars6 = new char[]{'Z','P','Y','S'};
private static final char [] chars7 = new char[]{'E','F'};

public static String getAequilateRandomStr(){
    int resultArray[] = getRandomWeightArray();
    StringBuffer strbuf = new StringBuffer();
     
    int i = 0;
    for(int j=0;j<resultArray.length;j++){
        switch(resultArray[j]){
            case 134:{
                i = (int) (Math.random()*chars1.length);
                strbuf.append(chars1[i]);
                break;
            }
            case 159:{
                i = (int) (Math.random()*chars2.length);
                strbuf.append(chars2[i]);
                break;
            }
            case 148:{
                i = (int) (Math.random()*chars3.length);
                strbuf.append(chars3[i]);
                break;
            }
            case 140:{
                i = (int) (Math.random()*chars4.length);
                strbuf.append(chars4[i]);
                break;
            }
            case 130:{
                i = (int) (Math.random()*chars5.length);
                strbuf.append(chars5[i]);
                break;
            }
            case 118:{
                i = (int) (Math.random()*chars6.length);
                strbuf.append(chars6[i]);
                break;
            }
            case 108:{
                i = (int) (Math.random()*chars7.length);
                strbuf.append(chars7[i]);
                break;
            }
            case 113:{
                strbuf.append('T');
                break;
            }
            case 100:{
                strbuf.append('L');
                break;
            }
            case 79:{
                strbuf.append('J');
                break;
            }
            case 56:{
                strbuf.append('I');
                break;
            }
            case 200:{
                strbuf.append('W');
                break;
            }
            case 194:{
                strbuf.append('M');
                break;
            }
        }
    }
     
    return strbuf.toString();
}

private static int[] getRandomWeightArray() {
    int slen = 6;
    int av = 793;
    
    int total = 0;
    int[] pos = new int[slen];
    Random rand = new Random();
    while (Math.abs(total - av) > 10) {
        total = 0;
        for (int i = 0; i < slen; i++) {
            pos[i] = WEIGHT[Math.abs(rand.nextInt()) % 26];
            total += pos[i];
        }
    }

    return pos;
}

public static void main(String[] args) {
    for(int i=0;i<40;i++){
      System.out.println(getAequilateRandomStr());
  }
}


等宽小写字母字符串(长度为6)的算法代码如下:

// 24个字母(剔除了o和l)+8个数字(剔除了0和1)各自的宽度
private static final int[] LWEIGHT = new int[] { 189, 161, 129, 129, 
    129, 129, 129, 123, 123, 118, 118, 118, 118, 118, 118, 118, 118, 
    118, 111, 111, 111, 111, 111, 102, 102, 102, 89, 78, 70, 70, 51, 51 };
// 按宽度分组
private static final char [] LOW1 = new char[]{'q','d','g','b','p'};
private static final char [] LOW2 = new char[]{'h','n','u'}; 
private static final char [] LOW3 = new char[]{'2','3','4','5','6','7','8','9'};
private static final char [] LOW4 = new char[]{'e','a','k','y','v'};
private static final char [] LOW5 = new char[]{'c','x','z'};
private static final char [] LOW6 = new char[]{'t','f'};
private static final char [] LOW7 = new char[]{'j','i'};

public static String getAequilateRandomLowStr(){
    int resultArray[] = getLowWeightArray();
    StringBuffer strbuf = new StringBuffer();
     
    int i = 0;
    for(int j=0;j<resultArray.length;j++){
        switch(resultArray[j]){
            case 129:{
                i = (int) (Math.random()*LOW1.length);
                strbuf.append(LOW1[i]);
                break;
            }
            case 123:{
                i = (int) (Math.random()*LOW2.length);
                strbuf.append(LOW2[i]);
                break;
            }
            case 118:{
                i = (int) (Math.random()*LOW3.length);
                strbuf.append(LOW3[i]);
                break;
            }
            case 111:{
                i = (int) (Math.random()*LOW4.length);
                strbuf.append(LOW4[i]);
                break;
            }
            case 102:{
                i = (int) (Math.random()*LOW5.length);
                strbuf.append(LOW5[i]);
                break;
            }
            case 70:{
                i = (int) (Math.random()*LOW6.length);
                strbuf.append(LOW6[i]);
                break;
            }
            case 51:{
                i = (int) (Math.random()*LOW7.length);
                strbuf.append(LOW7[i]);
                break;
            }
            case 189:{
                strbuf.append('m');
                break;
            }
            case 161:{
                strbuf.append('w');
                break;
            }
            case 89:{
                strbuf.append('s');
                break;
            }
            case 78:{
                strbuf.append('r');
                break;
            }
        }
    }
     
    return strbuf.toString();
}

private static int[] getLowWeightArray() {
    int slen = 6;
    int av = 670;
    
    int total = 0;
    int[] pos = new int[slen];
    Random rand = new Random();
    while (Math.abs(total - av) > 10) {
        total = 0;
        for (int i = 0; i < slen; i++) {
            pos[i] = LWEIGHT[Math.abs(rand.nextInt()) % 26];
            total += pos[i];
        }
    }
    return pos;
}

public static void main(String[] args) {
    for(int i=0;i<40;i++){
      System.out.println(getAequilateRandomLowStr());
  }
}

示例:

生成的等宽字符串如下,

FDLQSQ

UVSZUB

HEKPVN

HECMFF

LQPHXC

DLLZWY

DSRXBV

XUCSPA

GTAPHY

IMVXVB

VGKPDT

JHQHFD

ZWBYLB

AVCPCX

EBFJOW

ZBBMZF

IBWUAS

EFONHP

yecydx

zcy8nk

kxvv9h

z54hkc

897z9c

8yckv6

ayexqe

3eczna

pex45x

y2nxx7

qcgxzx

k3x96k

3zea29

zvxpxd

xkxyda

p8ccxu

zkx38e