Deltamaster Tech Center

  public static final int getDistance(String word, String similar) {

    //get the weights for each possible operation
    final int costOfDeletingSourceCharacter = config.getInteger(Configuration.COST_REMOVE_CHAR);
    final int costOfInsertingSourceCharacter = config.getInteger(Configuration.COST_INSERT_CHAR);
    final int costOfSubstitutingLetters = config.getInteger(Configuration.COST_SUBST_CHARS);
    final int costOfSwappingLetters = config.getInteger(Configuration.COST_SWAP_CHARS);
    final int costOfChangingCase = config.getInteger(Configuration.COST_CHANGE_CASE);

    int a_size = word.length() + 1;
    int b_size = similar.length() + 1;
    int[][] matrix = new int[a_size][b_size];
    matrix[0][0] = 0;

    for (int i = 1; i != a_size; ++i)
      matrix[i][0] = matrix[i - 1][0] + costOfInsertingSourceCharacter; //initialize the first column

    for (int j = 1; j != b_size; ++j)
      matrix[0][j] = matrix[0][j - 1] + costOfDeletingSourceCharacter; //initalize the first row

    word = " " + word;
    similar = " " + similar;

    for (int i = 1; i != a_size; ++i) {
      char sourceChar = word.charAt(i);
      for (int j = 1; j != b_size; ++j) {

        char otherChar = similar.charAt(j);
        if (sourceChar == otherChar) {
          matrix[i][j] = matrix[i - 1][j - 1]; //no change required, so just carry the current cost up
          continue;
        }

        int costOfSubst = costOfSubstitutingLetters + matrix[i - 1][j - 1];
        //if needed, add up the cost of doing a swap
        int costOfSwap = Integer.MAX_VALUE;
        boolean isSwap = (i != 1) && (j != 1) && sourceChar == similar.charAt(j - 1) && word.charAt(i - 1) == otherChar;
        if (isSwap)
          costOfSwap = costOfSwappingLetters + matrix[i - 2][j - 2];

        int costOfDelete = costOfDeletingSourceCharacter + matrix[i][j - 1];
        int costOfInsertion = costOfInsertingSourceCharacter + matrix[i - 1][j];

        int costOfCaseChange = Integer.MAX_VALUE;
        String strSrcChar = "" + sourceChar;
        String strOtherChar = "" + otherChar;

        if (strSrcChar.compareToIgnoreCase(strOtherChar) == 0)
          costOfCaseChange = costOfChangingCase + matrix[i - 1][j - 1];

        matrix[i][j] = minimum(costOfSubst, costOfSwap, costOfDelete, costOfInsertion, costOfCaseChange);
      }
    }
    int cost = matrix[a_size - 1][b_size - 1];

    if (false)
      System.out.println(dumpMatrix(word, similar, matrix));

    return cost;
  }

　　最近有一个关于在大规模的中英文词库中的模糊搜索问题。

　　这个问题具有几个特点：

• 每条记录都比较短。
• 记录的数量多，大约600万条记录。
• 对解的数量要求高于对解的质量要求。
• 有对中英文支持的要求。

　　对于单一的字符串模糊匹配问题，实际上是单纯的人工智能问题，站在模式识别的角度，就是计算与目标单词的距离，我们实际上需要通过求最一般合一来算出单词之间的编辑距离，这个编辑距离越大，匹配度就越低。如果想更进一步，那么借助遗传算法的思想，随着用户的操作来动态调整每一步编辑的权值（默认所有编辑行为的权值都为1），如果用户认可某次匹配，则对此次匹配所用到的所有编辑行为降低权值。

　　而对于这样的一个实际问题，首先我们不可能将600万条记录全部取出逐一检测匹配度，势必要进行一个事先的筛选。因此，大致的流程应该是这样：

1. 针对所有数据建立倒排索引。
2. 从索引查找到疑似的匹配项。
3. 对疑似匹配项的匹配度进行逐个检查，去掉匹配度低的结果。
4. 按匹配度从高到低输出结果。

　　针对此问题，还有以下一些问题需要解决。

　　而求编辑距离必须使用基于代价函数的广度优先搜索，否则，无法保证最优解，在权值全部相同的情况下，就等同于一般的广度优先搜索，修改步数增加以后，内存开销明显增加。

　　为了减小索引，加快索引速度，必须要合并类似的索引项，对于中文，根据拼音-汉字库将汉字一律合并至为对应拼音是可行的。

　　但是对于英文，不可能以字符为单位进行索引，而如果以单词为单位进行索引，拼写错误就无法从索引中找出相应项。如果对无法找到的项进行广度优先的编辑，试图从索引中找出最近似的条目，对于索引查询的开销也是极高的。

　　单词拆分对索引也是一个考验，因为如果某个单词无法匹配，其实则可能可以进行拆分，比如helloworld，有9种方法分成两个单词，那么需要对9种拆分方法逐个进行查询，开销也是很大的。如果在这个基础上再考虑拼写错误，那么开销就是平方级的增长了。

　　最近在考虑设计比较完整可扩展的权限控制机制，希望能够通过这种机制来集中进行权限控制，并借助AOP将权限控制与功能模块分离。

　　原始的做法来源于操作系统的ACL表，建立一张角色与权限的二维表格，角色与权限相交处的值就表示该角色是否具有该权限（或者用数值、集合代表拥有该权限的“程度”），使用查表的方式已经可以达成AOP控制的前提条件。不过，缺陷在于ACL表的表达能力有限，角色和权限都不具有层次性（无法利用继承性简化权限设定操作的复杂度）。

　　另一个问题是，如果一个用户可以拥有多个角色，那么当多个角色之间的权限设定值不同时应该如何取舍也是一个难题。

　　首先为了改善角色的层次性，将角色建立成树形的数据结构，即在数据库中新增一个parent字段（双亲表示法）指出其父角色，需要注意的是，父角色的权限较低，子角色继承了来自父角色的所有权限，还可以具有自己的权限。因此，处于Root的角色，实际上是整个应用中最低权限的角色（角色的默认权限）。对于这个角色的权限描述，则使用灵活性和语义都很强的JSON数组，JSON对象中的key就是权限的key，value就是权限设定值。

　　在继承性上，也同样遇到该用户具有的不同角色的权限设定可能不同的问题，也还不清楚子角色的权限继承行为具体是怎样的。为了解决这个问题，我们引入一个权限的positive属性，来标识该权限是一个积极的属性还是一个消极的属性，另外，还需要一个属性type来标识该权限是数值型、布尔型还是集合类型（在这里讨论这三种类型的权限）。

• 布尔型非常容易理解，就是“是”或“否”、“能”或“不能”，如果positive，就可以描述是否具备某种权限，否则可以描述是否具有某种限制。
• 数值型用来描述某种程度，例如“自我介绍的最大长度”、“最短发帖时间间隔”等，如果positive，则表示数值越大权限越高，否则数值越小权限越高。
• 集合类型表示一个特定的类别序列，例如“可以上传的文件类型”等，如果positive，则集合表示允许的类型序列，集合越大，允许操作的类别多，权限高，否则集合表示禁止的类型序列，集合越大，允许操作的类别越少，权限低。

　　基于这三种情况，我们首先考虑权限继承的问题，在考察某个角色的权限时，首先从该角色开始在JSON对象中搜索该操作所需的权限，无论找到与否都必须继续查找父角色中对该权限的设置，直至查找到根，这时我们自底向上取得了一系列对于该权限的设置，然后我们需要进行合成，合成根据上面权限的三种类型以及positive的值。

• 布尔型：positive表示对所有这些权限值进行或运算，即一旦出现true则结果为true；否则对这些权限值进行与运算，即一旦出现false则结果为false。
• 数值型：positive表示取所有权限值的最大值；否则取所有权限值的最小值。
• 集合类型：positive表示对所有权限值进行并运算；否则对所有权限值进行交运算。

　　如果一个用于具有多种角色，那么在计算得到每个角色的实际权限后，再根据上述规则合成这些角色的权限值。

　　根据上面的思路，角色已经成为树结构，但是权限还是普通表结构，因此，我们考虑允许权限的分组，将权限同样构造为具有层次的树结构。为了使树有意义，我们需要限定非布尔类型的权限只能出现在权限树的叶子节点上。这样，对于非叶子节点，既表示一种权限设置，又决定了其子权限设定是否有意义。

　　为了使得权限设置更加简单，我们甚至还可以引入三状态变量，表示Full、None或者Partial，加快了权限查找效率，有时也简化了某些权限的设定。

　　JS框架的另一个重要任务，就是控件的访问控制，即通过怎样的方式访问一个控件，如何保证不丢失引用，以及如何确保控件可见性的合理和安全。

　　控件的继承是一个额外的问题，因为控件公共的属性和方法太多是需要使用继承特性的一个重要原因，而另一个重要原因则是为了使用多态性带来的便利。JavaScript的语法决定了，在JavaScript中实现多重继承是可行的，多重继承写法可以有意识地写成类似接口继承的形式，避免混淆的对象引用。

　　例如，一个Form控件，要如何控制允许出现在其中的控件类型呢？比较合理的做法就是，将文本框、单选框、提交按钮等抽象FormItem的基类即可。某种控件里，应该限定允许存在的控件类型。

　　一般情况下理想情况是，组合关系不可以形成环，但是有时形成环是无法避免的，这时候框架必须小心避免实际控件的循环包含关系，否则将导致无穷递归包含的现象发生。因此，要由框架来限制环的形成（毕竟无穷递归的广义表只是理论上研究的数据结构）。

　　站在安全可控的角度，我们不应该让使用者用new关键字来建立一个控件，使用new建立的控件意味着框架无法得知控件的引用情况，这对于面向对象的界面控制是一种灾难，因为既无法保证安全的可见性，也无法保证不发生引用丢失。不安全的可见性就意味着，框架将无法感知控件的更改，而丢失引用意味着一些DOM没有逻辑控件对象可以操控。

　　因此，我们往往通过父对象的方法来创建一个子对象，这个子对象的可见性自然处于父对象之中，由框架感知、掌控其所有操作和引用计数。这时候程序员的设计方法就变成，先创建父对象，然后向其中添加子对象，与使用new关键字方式创建控件的常见实现正好相反。

　　不过这自然会导致代码复用性的问题，因为基于这种方式就意味着无法直接使用已经创建好的控件。对于这个问题的解决方案是，重用用于创建这个控件的选项参数，而不是重用这个控件本身。

　　站在消息传递的角度，控件产生的消息只能由其创建者捕获，父控件捕获消息后，自行处理或将其转发到合适的子控件的处理队列中。这种消息传递机制非常严格，类似于树形网络的消息传递，是非常严谨可靠的，但是不可避免对于开发效率有一定的影响。这种写法是有长远的好处的，因为如果程序员无法明确控件的父子关系，那么很有可能无法预料异常结果的发生。

　　纯JS实现的Web界面框架，被认为是一种基于组件的管理方式，可以认为是在浏览器上近似实现桌面应用GUI的方式。Web组件的封装与桌面控件的实现不同，JS框架需要通过封装来做的，就是管理与其逻辑结构相关联的DOM元素；而这两者在思想上却具有相似的地方（这是一定的，因为本质上这是一种主动的模仿）。

　　因此有以下几个问题需要关心：

1. 封装必然导致的问题就是灵活性受限，提供的API不可能是完备的。用户如果跨越框架直接操纵DOM，将是非常不可靠的，框架的更新或者仅仅简单的界面风格切换，都可能导致用户的越级操作失效。因此，接口提供用户需要的尽可能多的功能，是非常必要的。
2. 对于控件的操作，应该总是从逻辑对象入手，由框架操作DOM对象，就像Windows编程时程序员会得到控件句柄，而控件句柄永远是指向了该控件的逻辑结构所在的空间，而不是二维层缓冲区。因此，一个逻辑控件的构造与析构，与实际控件是否在缓冲区或被释放，是没有直接的联系的（对JS来说，就是与DOM对象的存在与否没有关系）。
3. 理论上良好的实现是需要时才产生DOM，而不是在构造时就产生DOM，尽管由于浏览器的优化行为，构造一个不用显示的DOM，计算开销是比较小的，然而还是由于浏览器的优化行为（空间换时间），DOM往往必须占据不少内存空间，远大于控件逻辑对象。实际上程序员是比较习惯手动控制DOM的创建和移除，因此许多框架中程序员都需要明确向框架发出构造DOM的指示，这就要求程序员对与何时构造DOM有一个基本的考虑。
4. 意图不明确的封装是糟糕的。如果在控件的逻辑结构上需要再进行一次封装，那么最好有明确的理由和完整的架构考虑，就像在Windows的C库上封装的MFC，甚至虚拟机。当然，使用MFC的程序员，往往不再同时直接接触Windows API，因为那样是被视为混乱的程序结构。然而在架构不明确的框架中，使用不同层次的框架往往是难免的，这样将同样产生不可靠的操作。另外，除了造成内聚性差以外，层次不明确导致开发人员也无法知道，使用哪一层的操作才是最优的，往往可能导致不同的实现，代码可读性也变差。
5. 框架要提供必要的文档，帮助开发人员了解，对逻辑控件的操作，会如何影响用户交互。
6. 不能够直接操纵逻辑对象的数据成员，因为直接操作数据成员一般都是不好的行为，而应该总是使用方法来进行调用，尽管JS语法上并没有可见性修饰符，但是从封装性的角度而言是不希望用户这样操作的。因此，对于可以修改的数据成员，总是应该提供修改/获取它们的值的方法。

　　Hibernate将对象分为瞬时（transient）、持久（persistent）和脱管（detached）三种状态。

　　使用new关键字构造的对象，都处于瞬时状态，经过save以后可以变成持久态，而由get或者load方法得到的对象，都处于持久态，而持久态对象在session结束以后，自动转入脱管态。

　　对于持久态的对象，只要使用相应的setter方法改变其属性值，这些改变就会被侦测到，在调用session的flush方法时该对象的所有变更都会被更新到数据库中，因此，对于持久态的对象，是不需要使用update方法对对象进行更新的。

　　对于脱管态的对象，使用setter方法对属性进行的变更不会被侦测到并自动应用到数据库，但是通过update方法可以将这些变更应用到数据库，并使对象重新进入持久态，而使用merge方法，同样可以将变更应用到数据库，但对象仍然处于脱管状态。

　　对于update、saveOrUpdate和merge三个方法，其实是有较大的区别的，有时候理解有误可能导致预料之外的结果。

　　saveOrUpdate方法的实际操作是：

1. 如果对象已经处于持久态，不作任何操作，返回。
2. 如果对象与另一个和session相关的对象拥有相同的标识符，则抛掷异常。
3. 如果对象没有为标识符属性赋值，则save。
4. 如果对象的标识符属性是用户调用setter方法赋值的，则save。
5. 如果对象的版本属性与赋予新实例对象的值相同，则save。
6. 否则update对象。

　　update方法的实际操作是：

1. 如果对象已经处于持久态，不作任何操作，返回。
2. 如果对象与另一个和session相关的对象拥有相同的标识符，则抛掷异常。
3. 如果对象没有为标识符属性赋值，则抛掷异常。
4. 如果对象的标识符属性是用户调用setter方法赋值的，则抛掷异常。
5. 如果对象的版本属性与赋予新实例对象的值相同，则抛掷异常。
6. 否则更新对象。

　　merge方法的实际操作是：

1. 如果有一个持久态对象与之具有相同标识符，则将这个对象的属性应用到相应的持久态对象上。
2. 否则load产生一个持久态对象，并将属性应用到这个持久态对象上。
3. 返回持久态的对象。
4. 传入merge方法的对象仍然处于脱管态或者瞬时态。

　　和一些面向对象的语言一样，JavaScript也支持this关键字，顾名思义，this关键字指代本对象，在传统的面向对象语言中，this代表该方法所属的对象，或者该对象的指针。

　　在JavaScript中没有类的概念，this方法的指代含义也有些许的变化，指代的是调用该方法的对象。

　　还是以上次的程序作为例子：

var User = function() {
	this.username = 'username';
	this.password = 'password';
}

User.prototype.toString = function() {	
	return this.username + ':' + this.password;
};

　　toString方法中就使用了this关键字来指代调用者本身，一般情况下，调用者和该方法的所属对象是一致的，这种情况下，就与其他语言没什么不同。不过，JavaScript中调用者和方法所属的对象并不一定是一致的，许多情况下与闭包特性结合，也能产生许多特殊的效果。下面是一个稍微复杂的例子。

var x = function() {
	this.show = function(msg, func, scope) {
		document.write(msg + " : " + this.value + '<br />');
		if (scope === undefined)
			scope = this;
		func.apply(scope, []);
		func.call(scope);
	}
};

var y = new x();
x.prototype.value = 4;

y.value = 5;

var z = new x();
z.value = 6;

var w = new x();
x.prototype.value = 7;

y.show('value is', function() {
	document.write('value in scope : ' + this.value + '<br />');
}, z);

y.show('value is', function() {
	document.write('value in scope : ' + this.value + '<br />');
}, x.prototype);

y.show('value is', function() {
	document.write('value in scope : ' + this.value + '<br />');
}, w);

　　x构造函数定义了一个show方法，首先输出调用者的value值，然后如果scope没有传入，则定义为方法的调用者本身。

　　随后出现了两个方法，分别为apply和call，这两个方法是所有function都具有的，作用是强制指定某对象作为该方法的调用者，两者除了调用格式略有不同，作用是相同的。这两句话以scope的身份调用了func。

　　后面定义了y、z、w三个变量，都分别是x的实例，接着以y的身份调用了3次show方法，只有scope参数传入了不同的值。

　　第一次传入了对象z，此时y作为show的调用者，而show中的参数匿名函数func的调用者却被设定为z，因此输出结果为：

value is : 5
value in scope : 6
value in scope : 6

　　第二次传入x.prototype，原理如上面相同，show的func参数是由x.prototype调用的，因此输入结果为：

value is : 5
value in scope : 7
value in scope : 7

　　第三次传入了对象w，原理也和上面相同，func的调用者是w，那么此时w的值是多少呢？我们在实例化w以后，我们修改了x.prototype.value的值，那么此时w的value应该是x.prototype.value修改前的值还是修改后的值呢？

　　答案是修改后的值，结果是：

value is : 5
value in scope : 7
value in scope : 7

　　因为w并没有显式定义value属性，因此w的value属性是位于其__proto__属性中，也就是x.prototype的引用，因此当x.prototype发生了改变，对于w也是会同时产生影响，具体关于prototype的原理和行为，请参考之前的其他文章。

　　上次讲到了JavaScript实现封装的特性，那么JavaScript能否模拟继承的特性呢？

var User = function() {
	this.username = 'username';
	this.password = 'password';
}

User.prototype.toString = function() {	
	return this.username + ':' + this.password;
};

　　这个是上次所写的User的定义。现在我们要新建一个Student，使其具有User的所有属性，和就类似与继承特性。

var extend = function(derived, base) {
	baseObj = new base();
 	for (property in baseObj) {
 		derived.prototype[property] = baseObj[property];
 	}
}

var Student = function() {
	this.studentNumber = '11111';
}

extend(Student, User);

var student = new Student();

document.write(student);

　　extend方法是为了模拟继承特性，函数体很简单，首先新建一个“基类”的对象，然后将“基类”对象中的所有属性，放到“派生类”的prototype中，就使得derived的对象可以访问到所有base对象具有的属性。

　　实际操作时，我们首先创建一个Student，并且定义其相对与User不同的部分。随后调用extend函数进行“继承”，使其具有User构造的对象的所有属性。

　　然后尝试使用Student来构造一个student对象。

　　JavaScript并不是一种面向对象的程序设计语言，严格来讲，它并没有什么类的概念，顶多只是JSON对象而已，然而在JavaScript中有prototype这个关键字，利用它，我们可以间接地实现一些面向对象的特性。

var User = function() {
	this.username = 'username';
	this.password = 'password';
	this.toString = function() {	
		return this.username + ':' + this.password;
	}
}

var user = new User();
document.write(user + '<br />');

　　这是一个很简单的封装实现，此时的User可以被视为一个“类”，这里还有一个方法叫做toString，实际上，在需要字符串的地方，对象的toString方法会自动被调用。

　　如果在上面这个例子中，toString没有被定义在User里面，也可以通过prototype关键字来定义在外部，效果是等价的。

User.prototype.toString = function() {
	return this.username + ':' + this.password;
};

　　如果在这个例子中没有写prototype关键字，那么user对象实际上是没有toString这个函数可以调用的，因为没有prototype代表这个toString函数仅被定义在User本身之上。

　　这是什么原理呢？

　　首先，使用new关键字进行新对象user的构造时，是调用了上面赋值给User的匿名函数，这个函数赋予了新对象user一些属性，就像在函数体中所写的那样。如果toString没有被定义在里面，那么此时user只有username和password两个属性。

　　如果在外部定义的toString没有加上prototype关键字，那么会发生什么情况呢？User对象具有了toString方法，然而User本身却没有username和password。因此，此时User的username与password均为undefined，有没有觉得比较像面向对象语言中的静态方法呢？是的，相同点在于：我们可以通过“类名”直接调用该方法，该方法不能使用“非静态”成员。

　　如果在toString被定义在User.prototype之下，user对象就会具有toString方法，这是为什么呢？因为每个对象都隐含了一个名为__proto__的属性，相当于在User构造函数的最后增加了：

this.__proto__ = User.prototype; //注意，这个__proto__是内部名称，不同浏览器实现不同名称也可能不相同。

　　prototype这个特殊的属性在构造函数定义时被初始化，初始化时包含了User的构造函数本身和自己的__proto__属性，当用户通过User.prototype的方式定义新属性或方法的时候，这些属性或方法就被增加到User.prototype这个JSON对象之中。由于this.__proto__ = User.prototype;的缘故，调用这个构造函数构造的所有对象的__proto__属性中，都包含有这个新属性或方法。因此，实际上toString并没有成为user下的一个方法，而是user.__proto__下的一个方法。

　　然后，实际执行user.toString()时，浏览器将检查user是否具有toString方法可以调用，如果没有，浏览器将继续检查其__proto__属性中是否有toString方法，如果仍然没有，则继续递归向上寻找这个__proto__属性的__proto__属性。如此，就可以解释为什么prototype下定义的方法，都可以被该“类”的所有实例调用的原因了。

　　JavaScript作为一种非常奇特的动态脚本语言，具有一些特有的语法特性，其中匿名函数和闭包特性可以说很大程度上区别了JavaScript程序设计与其他传统语言程序设计的方法。

匿名函数：

var x = function() {
	document.write('hello world!');
};

x();

　　上面这个例子是一个最简单的匿名函数，显而易见的事实有三点：第一，函数没有被命名；第二，函数以对象的形式赋值给变量x；第三，我们也可以通过变量名x来调用这个函数。这使得函数能够非常方便地以参数的形式进行传递。

闭包：

　　关于闭包特性有许多复杂的解释，但是为了便于理解，简单来说就是，一个变量的作用域或者生命期，与其所在的源代码中的位置有关，而不是与运行时的上下文相关。下面是一个关于闭包的小例子（来自维基百科）：

function derivative(f,  dx) {
	return  function (x) {
		return (f(x + dx) - f(x)) / dx;
	};
}

var result = derivative(function(x) {
	return x * x;
}, 0.000001)(5);

document.write(result + '<br />');

　　上面的代码实际上是在求函数某一点上的近似的导数值。

　　derivative这个函数接受两个参数，f应该是接受一个数值型变量的函数，dx应该是一个很接近0的浮点数。然而derivative实际上并没有返回一个确切的导数值，因为并没有得到需要求解的确切的横坐标的值，因此返回了原函数f的导函数。请注意，有一个只接受一个参数x的匿名函数作为返回值被derivative函数返回了。

　　下面定义了result变量，首先调用derivative求导函数，需要传入两个参数，f传入了一个匿名函数x平方，dx按照要求传入一个很小的值0.000001（你也可以取得更大一些或更小一些）。接着应该就得到了一个导函数，再为导函数传入常量参数5，得到了x平方在x=5这一点上的近似导数值，输出的结果非常接近10，也是我们期待的结果。

　　接下来反过来看一看函数执行的实际过程。

1. derivative函数被定义。
2. derivative被调用，此时derivative函数得到的实参分别是f=function(x) {return x * x;}和dx=0.000001。
3. 函数返回一个函数function (x) { return (f(x + dx) - f(x)) / dx; }。
4. 随后调用这个刚刚被返回的函数，实参是x=5。请注意，按照传统语言的变量作用域，此时derivative函数应当早已退出堆栈，其参数f和dx的值应当早已不在内存，而在JavaScript中，此时f和dx的值却仍然保留为derivative函数被调用时的值，仅因为这个匿名函数被写在了derivative函数的内部。