常见算法

  • 编辑距离算法（EditDistance）
  • n-gram算法
  • JaroWinkler算法
  • Soundex算法
  • 基于神经网络的算法

编辑距离算法

最常见的相似度算法为编辑距离算法（EditDistance），该算法将两个字符串的相似度问题，归结为将其中一个字符串转化成另一个字符串所要付出的代价。转化的代价越高，说明两个字符串的相似度越低。通常可以选择的转化方式包含插入，替换以及删除。

N-Gram算法

N-Gram算法则是基于这样的一个假设： 即在字符串中第n个词的出现只与前面n-1个词相关，而与其他任何词都不相关，整个字符串出现的概率就是各个词出现的概率的乘积。 N-gram本身也代表目标字符串中长度为n的子串，举例，“ARM”在“ARMY”中，便是一个3-gram。当两个字符串中，相同的n-gram越多时，两个字串就会被认为更加相似。

JaroWinkler算法

Jaro Winkler则是将n-gram算法更进了一步。将n-gram中的不匹配的部分同时进行了换位的考虑，使得能获得更准确的相似程度。JaroWinkler在比较两个较短字符串的情况下，能够取得很好的结果。

Soundex算法

Soundex算法与前面几种都不太相同。该算法的特点是，它所关注的问题并非两个字符串文本上的相似程度，而是发音的近似。首先，该算法会将两个字符串分别通过一定的hash算法转换成一个hash值，该值由四个字符构成，第一个字符为英文字母，后面三个为数字。进行转化的hash算法并非随机选取，而是利用了该拉丁文字符串的读音近似值。 当获得了两个字符串的读音上的hash值之后，该算法再对两个hash的相似度进行计算，便可以得出输入字符串的读音相似度。 Soundex算法的另一个应用场景在于，用户进行模糊查询时，可以通过Soundex值进行过滤，以提高查询性能。

中文相似度

以上算法在拉丁文中能够起到很好效果，但在中文中却存在较多问题，问题主要如下：

  • 同音字： 转换成拼音
  • 方言易混淆发音字： 音标转换 L-N AN-ANG 等
  • 字形相似：四角编码

音形码，对拼音和形状分别进行编码和计算相似度，最后求一个综合相似度。

tip：使用大规模训练数据对字进行embedding计算相似度。

LSTM implement with keras

import keras
from keras.layers import Input, LSTM, Dense
from keras.models import Model

tweet_a = Input(shape=(280, 256))
tweet_b = Input(shape=(280, 256))

# This layer can take as input a matrix
# and will return a vector of size 64
shared_lstm = LSTM(64)

# When we reuse the same layer instance
# multiple times, the weights of the layer
# are also being reused
# (it is effectively *the same* layer)
encoded_a = shared_lstm(tweet_a)
encoded_b = shared_lstm(tweet_b)

# We can then concatenate the two vectors:
merged_vector = keras.layers.concatenate([encoded_a, encoded_b], axis=-1)

# And add a logistic regression on top
predictions = Dense(1, activation='sigmoid')(merged_vector)

# We define a trainable model linking the
# tweet inputs to the predictions
model = Model(inputs=[tweet_a, tweet_b], outputs=predictions)

model.compile(optimizer='rmsprop',
              loss='binary_crossentropy',
              metrics=['accuracy'])
model.fit([data_a, data_b], labels, epochs=10)

参考