作者： 龙心尘

时间：2021年1月

出处：https://blog.csdn.net/longxinchen_ml/article/details/113074403
其实这是一个不太好解释的问题，因为并没有一个完备的定义。笔者在算法领域遇到了不少同行，发现各自的工作侧重点甚至思维方式都很不同。为了给入门的朋友一个清晰的梳理，这里就简单串一串12个常见的算法。

首先，全景图镇楼。


算法与非算法的区别
一般来说，可以把编程工作分为两种，一种是面向实现的，一种是面向优化的。前者如实现一个功能、搭建一个服务、实现一种展现交互方式等。更关注的是如何实现功能，如何对于各种复杂甚至小众的场景都不出错。互联网中典型的后端、前端、平台、网络工程师的主要工作是这一类。



如果一些功能已经实现了，你主要需要优化它，那这类工作一般比较偏向算法。其中一个关键是你的优化目标要是客观可量化的。比如一些代码优化的工作是提升代码的可维护性、可读性和可扩展性。这个优化目标具备比较强的主观性，难以形成量化的指标，属于设计模式主要关注的问题，一般不纳入算法范畴。
另一个区分算法与非算法工作的重要特征是一般涉及数学知识较多的编程工作更偏向算法。比如对于面向优化的编程工作，为了很好地衡量可量化的目标，其数学定义往往比较明确，相应引入的数学知识会比较多。
那么如果面向实现的编程工作也依赖大量数学知识时是否算作算法呢？其中一个例子是可计算性理论，它涉及到可判定性问题、数理逻辑等问题都需要大量复杂的数学知识。这种情况下，它其实更关心何种问题原则上是否可用算法解决，在实际工程领域中并没有大量的岗位与之相匹配，所以本文暂不将其作为算法工程师所考虑的范围。


另一个例子是加密算法。加密算法的目标是保证数据的安全通信，保证其加密性、完整性和身份唯一确认。看起来是面向实现，但换一个视角，加密算法设计的指导思想是提高其解密成本，也可以算是面向优化的。


不同种类算法之间的区别
如果你的优化目标是要降低程序的时间复杂度与空间复杂度，它们都是能够比较严格地量化定义的，就属于经典的“数据结构与算法”中关注的“算法”的问题。LeetCode中大部分Algorithm的题目都属于此类，也是互联网面试中的高频考点，如常见的分治、递归、动态规划等。在实际工作中，特别是一些架构师相关的角色，会着重关注这类问题，比如提升增删改查的速度、降低其内存消耗等等。相应的数学理论是计算复杂性理论，依赖的数学知识包括离散数学、组合数学、图论等。



如果你的优化目标是要降低在未见过的case上的预测误差，这是典型的机器学习中的算法问题。这里面涉及到一些核心的概念，包括：泛化误差、训练误差、过拟合、欠拟合、偏差等。相应的算法岗位非常多，图像算法、语音算法、自然语言处理算法、搜索推荐算法等。
机器学习算法还可以根据优化目的的不同进行进一步的细分。如果训练数据带有标签，优化目标是降低预测标签的误差则是最常见的有监督学习。如果训练数据不带标签，则是无监督学习。而如果此时又非要预测对应的标签，则有降维和聚类两种算法。如果仅仅是为了拟合训练数据的分布，生成式算法。
它的数学理论是计算学习理论，依赖的数学知识包括概率与统计、最优化理论、线性代数与矩阵论等。



当然，最优化本身就是一种算法。稍微严格一点的表述是在一定的约束条件下控制自变量达到目标函数最优的问题。最优化问题也叫作运筹学，在工程界应用非常广泛。典型的如外卖骑手调度、网约车调度、航班调度、物流路径调度、广告/补贴金额投放等。


最优化算法的种类也比较多，以自变量是否连续可分为连续最优化和组合优化。很多计算复杂度优化算法可以看做一种广义的组合优化问题。机器学习算法一般是连续最优化问题。
不同算法思路的相互组合
其他一些的高阶算法可以理解为以上多种算法的组合。比如强化学习算法可以理解成机器学习中的有监督学习算法与最优化决策算法的组合。也就是智能体根据其对当前环境下长期最大收益进行决策（最优化），而这个收益的函数是需要通过大量样本统计（有监督学习）才能得到，并且智能体的当下决策往往影响周围的环境状态进而进一步影响下一步自身的决策。其典型应用场景是基于用户实时行为的个性化推荐与搜索，外卖骑手路径优化与订单分配的在线优化等。其实，“强人工智能”如果可行的话，强化学习是其绕不开的学习思路。



以上介绍的优化算法都是基于单智能体的，而博弈论就将其拓展到多个智能体的最优化，视野一下就打开了。多个智能体的优化策略是会相互影响的。也就是说多智能体各自基于各自的优化函数进行优化，并且各自的优化行动可以影响其他智能体优化策略的过程。博弈论算法典型的应用场景是拍卖竞价策略。在ACG文化中的《大逃杀》、《赌博默示录》、《弥留之国的爱丽丝》甚至《JOJO》等大量作品中都充满了大量的博弈论场景。有一个小程序的游戏叫作《信任的进化》，简单玩一下就能够体会到博弈论的有趣之处。



多智能体强化学习则是多个智能体的强化学习得到最优策略，并且各自的最优策略会影响对方智能体的下一步优化策略的过程。或者理解成其认为博弈论收益函数是不确定的，需要对通过大量样本统计(长期收益的有监督学习)。典型的案例是AlphaGo、AlphaZero之类。
生成对抗网络(GAN)有点特殊，可以理解成两种机器学习算法的组合，一种算法的优化目标是降低生成样本与真实样本的区分难度，另一种算法的优化目标是提升他们的区分难度。而这两个目标是相互对立的，这又借鉴了博弈论的思路。这类算法在图像风格迁移、图像修复等场景有非常多的应用。



另外，模型压缩算法可以理解成机器学算法与优化计算复杂度算法组合，在一定的误差容忍范围下显著降低模型的空间复杂度和推断时间复杂度。其典型应用场景是模型的实时运算加速、边缘部署压缩等。
小结一下
这里主要从面向优化的角度上串讲了以下12种思维方式不同的算法：加密算法、计算复杂度优化算法、最优化算法、有监督学习、无监督学习（降维、聚类、生成）、强化学习、博弈论、多智能体强化学习、生成对抗网络、模型压缩算法等。
因为是科普向，很多细节没展开，特别是机器学习算法和优化计算复杂度算法的各个流派没有探讨。
我们将在接下来的文章中进行更加详细的介绍。

遗传算法 

建立GeneticAlgorithm.py




import numpy as np
from GAIndividual import GAIndividual
import random
import copy
import matplotlib.pyplot as plt


class GeneticAlgorithm:

    '''
    The class for genetic algorithm
    '''

    def __init__(self, sizepop, vardim, bound, MAXGEN, params):
        '''
        sizepop: population sizepop 种群数量 60
        vardim: dimension of variables 变量维度 25
        bound: boundaries of variables 变量的边界 -600 600
        MAXGEN: termination condition  终止条件  1000
        param: algorithm required parameters, it is a list which is consisting of crossover rate, mutation rate, alpha
        算法所需的参数，它是由交叉率，变异率，alpha组成的列表
        0.9, 0.1, 0.5
        '''
        self.sizepop = sizepop
        self.MAXGEN = MAXGEN
        self.vardim = vardim
        self.bound = bound
        self.population = []
        #self.fitness 60行一列 全0填充
        self.fitness = np.zeros((self.sizepop, 1))
        #25行两列
        self.trace = np.zeros((self.MAXGEN, 2))
        self.params = params

    def initialize(self):
        '''
        initialize the population 初始化种群
        '''
        for i in range(0, self.sizepop):
            ind = GAIndividual(self.vardim, self.bound)
            #生成一个随机染色体
            ind.generate()
            self.population.append(ind)

    def evaluate(self):
        '''
        evaluation of the population fitnesses
        评估种群适合度
        '''
        for i in range(0, self.sizepop):
            #计算染色体适应性
            self.population[i].calculateFitness()

            self.fitness[i] = self.population[i].fitness

    def solve(self):
        '''
        evolution process of genetic algorithm
        遗传算法的演化过程
        '''
        self.t = 0
        self.initialize()
        self.evaluate()
        best = np.max(self.fitness)
        bestIndex = np.argmax(self.fitness)
        self.best = copy.deepcopy(self.population[bestIndex])
        #取平均适应度
        self.avefitness = np.mean(self.fitness)
        self.trace[self.t, 0] = (1 - self.best.fitness) / self.best.fitness
        self.trace[self.t, 1] = (1 - self.avefitness) / self.avefitness
        print("Generation %d: optimal function value is: %f; average function value is %f" % (
            self.t, self.trace[self.t, 0], self.trace[self.t, 1]))
        while (self.t < self.MAXGEN - 1):
            self.t += 1
            self.selectionOperation()
            self.crossoverOperation()
            self.mutationOperation()
            self.evaluate()
            best = np.max(self.fitness)
            bestIndex = np.argmax(self.fitness)
            if best > self.best.fitness:
                self.best = copy.deepcopy(self.population[bestIndex])
            self.avefitness = np.mean(self.fitness)
            self.trace[self.t, 0] = (1 - self.best.fitness) / self.best.fitness
            self.trace[self.t, 1] = (1 - self.avefitness) / self.avefitness
            print("Generation %d: optimal function value is: %f; average function value is %f" % (
                self.t, self.trace[self.t, 0], self.trace[self.t, 1]))

        print("Optimal function value is: %f; " %
              self.trace[self.t, 0])
        print ("Optimal solution is:")
        print (self.best.chrom)
        self.printResult()

    def selectionOperation(self):
        '''
        selection operation for Genetic Algorithm
        遗传算法的选择操作
        '''
        newpop = []
        totalFitness = np.sum(self.fitness)
        accuFitness = np.zeros((self.sizepop, 1))

        sum1 = 0.
        for i in range(0, self.sizepop):
            accuFitness[i] = sum1 + self.fitness[i] / totalFitness
            sum1 = accuFitness[i]

        for i in range(0, self.sizepop):
            r = random.random()
            idx = 0
            for j in range(0, self.sizepop - 1):
                if j == 0 and r < accuFitness[j]:
                    idx = 0
                    break
                elif r >= accuFitness[j] and r < accuFitness[j + 1]:
                    idx = j + 1
                    break
            newpop.append(self.population[idx])
        self.population = newpop

    def crossoverOperation(self):
        '''
        crossover operation for genetic algorithm
        交叉操作
        '''
        newpop = []
        for i in range(0, self.sizepop, 2):
            idx1 = random.randint(0, self.sizepop - 1)
            idx2 = random.randint(0, self.sizepop - 1)
            while idx2 == idx1:
                idx2 = random.randint(0, self.sizepop - 1)
            newpop.append(copy.deepcopy(self.population[idx1]))
            newpop.append(copy.deepcopy(self.population[idx2]))
            r = random.random()
            if r < self.params[0]:
                crossPos = random.randint(1, self.vardim - 1)
                for j in range(crossPos, self.vardim):
                    newpop[i].chrom[j] = newpop[i].chrom[
                        j] * self.params[2] + (1 - self.params[2]) * newpop[i + 1].chrom[j]
                    newpop[i + 1].chrom[j] = newpop[i + 1].chrom[j] * self.params[2] + \
                        (1 - self.params[2]) * newpop[i].chrom[j]
        self.population = newpop

    def mutationOperation(self):
        '''
        mutation operation for genetic algorithm
        变异操作。
        '''
        newpop = []
        for i in range(0, self.sizepop):
            newpop.append(copy.deepcopy(self.population[i]))
            r = random.random()
            if r < self.params[1]:
                mutatePos = random.randint(0, self.vardim - 1)
                theta = random.random()
                if theta > 0.5:
                    newpop[i].chrom[mutatePos] = newpop[i].chrom[
                        mutatePos] - (newpop[i].chrom[mutatePos] - self.bound[0, mutatePos]) * (1 - random.random() ** (1 - self.t / self.MAXGEN))
                else:
                    newpop[i].chrom[mutatePos] = newpop[i].chrom[
                        mutatePos] + (self.bound[1, mutatePos] - newpop[i].chrom[mutatePos]) * (1 - random.random() ** (1 - self.t / self.MAXGEN))
        self.population = newpop

    def printResult(self):
        '''
        plot the result of the genetic algorithm
        画出结果
        '''
        x = np.arange(0, self.MAXGEN)
        y1 = self.trace[:, 0]
        y2 = self.trace[:, 1]
        plt.plot(x, y1, 'r', label='optimal value')
        plt.plot(x, y2, 'g', label='average value')
        plt.xlabel("Iteration")
        plt.ylabel("function value")
        plt.title("Genetic algorithm for function optimization")
        plt.legend()
        plt.show()

if __name__ == "__main__":
    bound = np.tile([[-600], [600]], 25)
    ga = GeneticAlgorithm(60, 25, bound, 1000, [0.9, 0.1, 0.5])
    ga.solve()

建立GAIndividual.py



import numpy as np
import ObjFunction

#个体的遗传算法
class GAIndividual:

    '''
    individual of genetic algorithm
    个体的遗传算法
    '''

    def __init__(self,  vardim, bound):
        '''
        vardim: dimension of variables 维度变量
        bound: boundaries of variables 变量的边界
        '''
        self.vardim = vardim
        self.bound = bound
        self.fitness = 0.

    def generate(self):
        '''
        generate a random chromsome for genetic algorithm
        为遗传算法生成一个随机染色体
        '''
        len = self.vardim
        rnd = np.random.random(size=len)
        self.chrom = np.zeros(len)
        for i in range(0, len):
            self.chrom[i] = self.bound[0, i] + \
                (self.bound[1, i] - self.bound[0, i]) * rnd[i]

    def calculateFitness(self):
        '''
        calculate the fitness of the chromsome
        计算染色体的适应性
        '''
        self.fitness = ObjFunction.GrieFunc(
            self.vardim, self.chrom, self.bound)

三建立ObjFunction.py



import math

#目标函数
def GrieFunc(vardim, x, bound):
    """
    Griewangk function
    经典函数girewangk
    """
    s1 = 0.
    s2 = 1.
    for i in range(1, vardim + 1):
        s1 = s1 + x[i - 1] ** 2
        s2 = s2 * math.cos(x[i - 1] / math.sqrt(i))
    y = (1. / 4000.) * s1 - s2 + 1
    y = 1. / (1. + y)
    return y

#非凸优化函数
def RastFunc(vardim, x, bound):
    """
    Rastrigin function
    在数学优化中，Rastrigin函数是一个非凸函数，用作优化算法的性能测试问题。这是一个非线性多模态函数的典型例子。它最初由Rastrigin [1]提出作为二维函数，并已被Mühlenbein等人推广。[2]寻找这个函数的最小值是一个相当困难的问题，因为它有很大的搜索空间和大量的局部最小值。

在一个n维域上，它被定义为：

{\ displaystyle f（\ mathbf {x}）= An + \ sum _ {i = 1} ^ {n} \ left [x_ {i} ^ {2} -A \ cos（2 \ pi x_ {i}）\对]} f（\ mathbf {x}）= An + \ sum _ {i = 1} ^ {n} \ left [x_ {i} ^ {2} -A \ cos（2 \ pi x_ {i}）\ right]
    """
    s = 10 * 25
    for i in range(1, vardim + 1):
        s = s + x[i - 1] ** 2 - 10 * math.cos(2 * math.pi * x[i - 1])
    return s

基于遗传算法的多目标算法 



#Importing required modules
import math
import random
import matplotlib.pyplot as plt


def function1(x):
    value = -x**2
    return value


def function2(x):
    value = -(x-2)**2
    return value

#Function to find index of list
#函数查找列表的索引
def index_of(a,list):
    for i in range(0,len(list)):
        if list[i] == a:
            return i
    return -1

#Function to sort by values 函数根据值排序
def sort_by_values(list1, values):
    sorted_list = []
    while(len(sorted_list)!=len(list1)):
        if index_of(min(values),values) in list1:
            sorted_list.append(index_of(min(values),values))
        values[index_of(min(values),values)] = math.inf
    return sorted_list

#Function to carry out NSGA-II's fast non dominated sort
#函数执行NSGA-II的快速非支配排序
"""基于序列和拥挤距离"""
def fast_non_dominated_sort(values1, values2):
    S=[[] for i in range(0,len(values1))]
    front = [[]]
    n=[0 for i in range(0,len(values1))]
    rank = [0 for i in range(0, len(values1))]

    for p in range(0,len(values1)):
        S[p]=[]
        n[p]=0
        for q in range(0, len(values1)):
             #p > q
            if (values1[p] > values1[q] and values2[p] > values2[q]) or (values1[p] >= values1[q] and values2[p] > values2[q]) or (values1[p] > values1[q] and values2[p] >= values2[q]):
                if q not in S[p]:
                    S[p].append(q)
            elif (values1[q] > values1[p] and values2[q] > values2[p]) or (values1[q] >= values1[p] and values2[q] > values2[p]) or (values1[q] > values1[p] and values2[q] >= values2[p]):
                n[p] = n[p] + 1
        if n[p]==0:
            rank[p] = 0
            if p not in front[0]:
                front[0].append(p)

    i = 0
    while(front[i] != []):
        Q=[]
        for p in front[i]:
            for q in S[p]:
                n[q] =n[q] - 1
                if( n[q]==0):
                    rank[q]=i+1
                    if q not in Q:
                        Q.append(q)
        i = i+1
        front.append(Q)

    del front[len(front)-1]

    return front

#Function to calculate crowding distance
#计算拥挤距离的函数
def crowding_distance(values1, values2, front):
    distance = [0 for i in range(0,len(front))]
    sorted1 = sort_by_values(front, values1[:])
    sorted2 = sort_by_values(front, values2[:])
    distance[0] = 4444444444444444
    distance[len(front) - 1] = 4444444444444444
    for k in range(1,len(front)-1):
        distance[k] = distance[k]+ (values1[sorted1[k+1]] - values2[sorted1[k-1]])/(max(values1)-min(values1))
    for k in range(1,len(front)-1):
        distance[k] = distance[k]+ (values1[sorted2[k+1]] - values2[sorted2[k-1]])/(max(values2)-min(values2))
    return distance

#Function to carry out the crossover
#函数进行交叉
def crossover(a,b):
    r=random.random()
    if r>0.5:
        return mutation((a+b)/2)
    else:
        return mutation((a-b)/2)

#Function to carry out the mutation operator
#函数进行变异操作
def mutation(solution):
    mutation_prob = random.random()
    if mutation_prob <1:
        solution = min_x+(max_x-min_x)*random.random()
    return solution

#Main program starts here
pop_size = 20
max_gen = 921

#Initialization
min_x=-55
max_x=55
solution=[min_x+(max_x-min_x)*random.random() for i in range(0,pop_size)]
gen_no=0
while(gen_no<max_gen):
    function1_values = [function1(solution[i])for i in range(0,pop_size)]
    function2_values = [function2(solution[i])for i in range(0,pop_size)]
    non_dominated_sorted_solution = fast_non_dominated_sort(function1_values[:],function2_values[:])
    print("The best front for Generation number ",gen_no, " is")
    for valuez in non_dominated_sorted_solution[0]:
        print(round(solution[valuez],3),end=" ")
    print("\n")
    crowding_distance_values=[]
    for i in range(0,len(non_dominated_sorted_solution)):
        crowding_distance_values.append(crowding_distance(function1_values[:],function2_values[:],non_dominated_sorted_solution[i][:]))
    solution2 = solution[:]

    #Generating offsprings
    while(len(solution2)!=2*pop_size):
        a1 = random.randint(0,pop_size-1)
        b1 = random.randint(0,pop_size-1)
        solution2.append(crossover(solution[a1],solution[b1]))
    function1_values2 = [function1(solution2[i])for i in range(0,2*pop_size)]
    function2_values2 = [function2(solution2[i])for i in range(0,2*pop_size)]
    non_dominated_sorted_solution2 = fast_non_dominated_sort(function1_values2[:],function2_values2[:])
    crowding_distance_values2=[]
    for i in range(0,len(non_dominated_sorted_solution2)):
        crowding_distance_values2.append(crowding_distance(function1_values2[:],function2_values2[:],non_dominated_sorted_solution2[i][:]))
    new_solution= []
    for i in range(0,len(non_dominated_sorted_solution2)):
        non_dominated_sorted_solution2_1 = [index_of(non_dominated_sorted_solution2[i][j],non_dominated_sorted_solution2[i] ) for j in range(0,len(non_dominated_sorted_solution2[i]))]
        front22 = sort_by_values(non_dominated_sorted_solution2_1[:], crowding_distance_values2[i][:])
        front = [non_dominated_sorted_solution2[i][front22[j]] for j in range(0,len(non_dominated_sorted_solution2[i]))]
        front.reverse()
        for value in front:
            new_solution.append(value)
            if(len(new_solution)==pop_size):
                break
        if (len(new_solution) == pop_size):
            break
    solution = [solution2[i] for i in new_solution]
    gen_no = gen_no + 1

#Lets plot the final front now
function1 = [i * -1 for i in function1_values]
function2 = [j * -1 for j in function2_values]
plt.xlabel('Function 1', fontsize=15)
plt.ylabel('Function 2', fontsize=15)
plt.scatter(function1, function2)
plt.show()

算法题目往往比较复杂，要么让人感到无从下手，要么很难给出一个最优解，但这恰恰是考验一个程序员思维方式的有效手段。看到这类的难题不要慌，《算法设计与分析基础》一书比较全面地总结了做算法题目的一些思路：
(1)蛮力穷举法，可以说可以解决所有的问题，不过对于组合数很大的问题时间性能不是很好甚至不能忍受。例子：全排列的生成、n选m组合的生成（这两个的蛮力法都可以利用多重嵌套循环形成，层次很壮观),8皇后问题(对应成8数全排列)，12城tsp问题(对应成12数排列),a的n次方计算就老老实实连乘n次a，顺序查找元素等都是蛮力穷举的例子。


(2)分治法，就是把1个大问题分成2个小问题，2个小问题还可以再分，直到问题规模小的可以简单解决。处理每个小问题，把处理结果汇总处理，最后得到整个大问题的解。一般而言，分治法都要用到递归。例子：算n个数的和，可以算前一半n/2的和，后一半n/2的和，最后相加即得总和；凸包问题，可以把最左边点和最右边点连线，右上边点集的凸包(叫做上包)和下面点集的凸包(叫做下包)，最后把上包和下包合围起来就是整个凸包。点集的最小点对问题，可以以一条线为界，分成左右两个集合，分别求最小点对，最后在合起来处理。分治法对多个处理器或处理机的并行计算特别适用。


(3)减治法，就是处理过程中问题规模不断减小的方法。最常见的就是折半查找，每次都把n/2个元素删去；减治法一半分为减1法，减常数法，减可变规模法。减1法典型的就是插入排序，还有计算a的n次方，可以计算a的n-1次方，再变成计算a的n-2次方等等。想查找二叉树的查找都利用了减治的思想。


(4)变治法，就是对问题进行变相，变化，利用已有的解决方案来解决生疏的问题，重点在于对原来的生疏问题进行转化，转变，使他变成一个已有好的解法的熟悉问题。 

(5)时空权衡，考虑时间和空间的相互转化，有时利用空间换时间，有时利用时间换空间，常用的就是  计数排序(多利用了一个计数数组)，散列法，B树。 

(6)动态规划，也是时空权衡的一种，把可重复的问题的解保存在一个表里面。例子包括   计算二项式系数，最有二叉查找树，背包问题和记忆功能。 

(7)贪婪算法，就是每一步都从可选方案中选择对该步最有利的方案，直到问题解决。贪婪法有可能得不到问题的最优解，不过得到的解一般都很接近问题的最优解。它的优点就是效率高，时间复杂性相对有那些得到最优解的算法快很多。常用的例子：


最小生成树的prim算法，kruskal算法，最短路径的dijkstra算法，解决tsp问题。 

(8)回溯法 

(9)分支限界法

在敏感词汇过滤这块，不同的算法所造成的性能差异是非常大的，选择一个合适的算法非常重要。因为以前做算法的时候做过类似前缀树的字符串匹配之类的算法，所以一开始就打算用前缀树做的，后面了解了一下DFA的相关算法原理，其实用在敏感词汇过滤这块，主要还是前缀树的应用。


这个算法最原始的实现我是采用的建立树结构的方式，发现性能还是不佳，最后借鉴了一些基于HashMap构造前缀树的方法来实现。算是使用比较广泛的算法了。在这里进行了完整的封装，并且做了一些小的优化。


这个算法并不是目前最好的敏感词过滤算法，但是比较容易理解，而且性能也不差，所以小的项目用这个也比较合适了。


0x01.关于DFA与前缀树

DFA（Deterministic Finite Automaton）：确定有穷自动机。
通俗理解DFA就是：从一个状态通过一系列的事件转换到另一个状态。
建立前缀树进行敏感词匹配的过程正是DFA的一种应用。
经过测试，使用HashMap建立的前缀树，确实比实际构造树结构的性能要好。

0x02.该算法的优缺点

优点：性能比较好，思想及实现都比较简单。
缺点：整个前缀树加载到内存中，如果敏感词比较多的话，那么消耗的内存会比较多。

0x03.完整代码（已封装好）


非静态方法，已封装好，创建对象后直接调用。


唯一需要修改的地方：具体敏感词汇的路径


具体注释在代码中。


提供三个方法：

getSensitiveWordNums：获取文本中敏感词汇的个数。
getSensitiveWordSet：获取文本中所有包含的敏感词汇。
replaceAllSensitiveWord：将文本中的敏感词汇替换成指定的词汇。



参数说明：

MIN_CONTAIN： 最少包含多少字才会被认定为敏感词。
minMatchTYpe： 单次匹配到一个敏感词汇后不继续匹配。
maxMatchType： 一直匹配直到文本结束。



import java.io.*;
import java.util.*;


@SuppressWarnings({ "rawtypes", "unchecked" })
public class SensitiveWordUtils {
    private String ENCODING = "UTF-8";//文件的字符编码
    private String PATH_RELATIVE="/src/main/resources/static/senc.txt";//敏感词汇相对项目的路径
    private HashMap sensitiveWordMap;//敏感词汇树
    private Integer MIN_CONTAIN=2;//包含敏感词的最多字数
    public static int minMatchTYpe = 1;      //最小匹配规则
    public static int maxMatchType = 2;      //最大匹配规则
    /**
     * 获取文本中敏感词汇的个数
     * @param txt 要检测的文本
     * @param beginIndex 开始的地方
     * @param matchType 匹配的规则
     * @return 敏感词汇的长度
     */
    public Integer getSensitiveWordNums(String txt,int beginIndex,int matchType){
        Set<String> wordSet = readSensitiveWordFromFile();
        addSensitiveWordToHashMap(wordSet);
        Integer result=0;
        for(int i = 0 ; i < txt.length() ; i++){
            //判断是否包含敏感字符
            int length = CheckSensitiveWord(txt, i, matchType);
            if(length > 0){    //存在,加入list中
                result++;
                i = i + length - 1;
            }
        }
        return result;
    }
    /**
     *
     * @param txt 检测的文本
     * @param matchType 匹配的规则
     * @return Set<String> 敏感词汇集合
     */
    public Set<String> getSensitiveWordSet(String txt , int matchType){
        Set<String> wordSet = readSensitiveWordFromFile();
        addSensitiveWordToHashMap(wordSet);
        return getSensitiveWord(txt,matchType);
    }
    /**
     *
     * @param txt
     * @param matchType
     * @param replaceChar 替换的词
     * @return 处理后的文本
     */
    public String replaceAllSensitiveWord(String txt,int matchType,String replaceChar){
        Set<String> wordSet = readSensitiveWordFromFile();
        addSensitiveWordToHashMap(wordSet);
        return replaceSensitiveWord(txt,matchType,replaceChar);
    }


    /**
     * 从文件中读取敏感词
     * @return 敏感词的Set集合
     */
    private Set<String> readSensitiveWordFromFile(){
        Set<String> wordSet = null;
        //获取项目路径
        String projectPath = System.getProperty("user.dir");
        //拼接得到敏感词汇的路径
        String path=projectPath + PATH_RELATIVE;
        File file = new File(path);
        try {
            //指定编码读取文件
            InputStreamReader read = new InputStreamReader(new FileInputStream(file), ENCODING);
            //判断文件是否存在
            if (file.isFile() && file.exists()) {
                //初始化wordSet
                wordSet = new HashSet<String>();
                //br用于读取文件的每一行
                BufferedReader br = new BufferedReader(read);
                String txt = null;
                while ((txt = br.readLine()) != null) {
                    wordSet.add(txt);
                }
                br.close();
            }else{
                throw new Exception("文件错误或文件不存在！");
            }
            read.close();

        } catch (UnsupportedEncodingException e) {
            e.printStackTrace();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        } catch (Exception e) {
            e.printStackTrace();
        }
        return wordSet;
    }

    //处理从文件得到的敏感词汇表，构造敏感词树

    /**
     * 将敏感词汇处理成敏感词汇树
     * @param keyWordSet 敏感词汇表
     */
    private void addSensitiveWordToHashMap(Set<String> keyWordSet){
        sensitiveWordMap = new HashMap(keyWordSet.size());
        String key = null;//读取的每一个关键字
        Map nowMap = null;//当前处理的map
        Map<String, String> newWorMap = null;//新建的map
        //用keyWordSet迭代器进行遍历
        Iterator<String> iterator = keyWordSet.iterator();
        while(iterator.hasNext()){
            key = iterator.next();
            nowMap = sensitiveWordMap;
            //遍历敏感词的每一位
            for(int i = 0 ; i < key.length() ; i++){
                //将一位转换位char类型
                char keyChar = key.charAt(i);
                Object wordMap = nowMap.get(keyChar);
                if(wordMap != null){  //如果存在该key，直接赋值
                    nowMap = (Map) wordMap;
                }else{   //不存在则，则构建一个map，同时将isEnd设置为0
                    newWorMap = new HashMap<String,String>();
                    newWorMap.put("isEnd", "0");     //不是最后一个
                    nowMap.put(keyChar, newWorMap);
                    nowMap = newWorMap;
                }
                if(i == key.length() - 1){
                    nowMap.put("isEnd", "1");    //最后一个
                }
            }
        }
    }

    /**
     * 获取文本中敏感词汇的个数
     * @param txt 要检测的文本
     * @param beginIndex 开始的地方
     * @param matchType 匹配的规则
     * @return 敏感词汇的长度
     */
    private int CheckSensitiveWord(String txt,int beginIndex,int matchType){
        boolean  flag = false;
        int matchFlag = 0;     //匹配标识数默认为0
        Map nowMap = sensitiveWordMap;
        char word = 0;
        for(int i = beginIndex; i < txt.length() ; i++){
            word = txt.charAt(i);
            nowMap = (Map) nowMap.get(word);//获取指定key
            if(nowMap != null){
                matchFlag++;     //找到相应key，匹配标识+1
                if("1".equals(nowMap.get("isEnd"))){       //如果为最后一个匹配规则,结束循环，返回匹配标识数
                    flag = true;       //结束标志位为true
                    if(minMatchTYpe == matchType){    //最小规则，直接返回,最大规则还需继续查找
                        break;
                    }
                }
            }else{
                break;
            }
        }
        return (matchFlag>=MIN_CONTAIN&&flag)?matchFlag:0;
    }

    /**
     *
     * @param txt 检测的文本
     * @param matchType 匹配的规则
     * @return Set<String> 敏感词汇集合
     */
    private Set<String> getSensitiveWord(String txt , int matchType){
        Set<String> sensitiveWordList = new HashSet<String>();
        for(int i = 0 ; i < txt.length() ; i++){
            //判断是否包含敏感字符
            int length = CheckSensitiveWord(txt, i, matchType);
            if(length > 0){    //存在,加入list中
                sensitiveWordList.add(txt.substring(i, i+length));
                i = i + length - 1;
            }
        }
        return sensitiveWordList;
    }
    //判断文字是否包含敏感字符

    /**
     * 检测是否包含敏感词
     * @param txt 检测的文本
     * @param matchType 匹配的规则
     * @return
     */
    public boolean isContaintSensitiveWord(String txt,int matchType){
        boolean flag = false;
        for(int i = 0 ; i < txt.length() ; i++){
            //判断是否包含敏感字符
            int matchFlag = this.CheckSensitiveWord(txt, i, matchType);
            //存在
            if(matchFlag > 0){
                flag = true;
            }
        }
        return flag;
    }

    /**
     *
     * @param txt
     * @param matchType
     * @param replaceChar 替换的词
     * @return 处理后的文本
     */
    private String replaceSensitiveWord(String txt,int matchType,String replaceChar){
        String resultTxt = txt;
        Set<String> set = getSensitiveWord(txt, matchType);
        Iterator<String> iterator = set.iterator();
        String word = null;
        String replaceString = null;
        while (iterator.hasNext()) {
            word = iterator.next();
            replaceString = getReplaceChars(replaceChar, word.length());
            resultTxt = resultTxt.replaceAll(word, replaceString);
        }

        return resultTxt;
    }

    //替换原本字符串
    private String getReplaceChars(String replaceChar,int length){
        String resultReplace = replaceChar;
        for(int i = 1 ; i < length ; i++){
            resultReplace += replaceChar;
        }
        return resultReplace;
    }
}

0x04.主要思路

读取文件里的敏感词汇到set集合中。
将set集合里的敏感词汇转换为HashMap形式的前缀树。
读取前缀树进行文本敏感词汇的判断。


GitHub地址：https://github.com/ATFWUS/Project-Algorithm/tree/master/Sensitive-word-filtering