精华内容
下载资源
问答
  • 算法工程师大致是什么的

    万次阅读 多人点赞 2021-01-25 22:37:39
    笔者在算法领域这些年遇到了不少做算法的同行,发现各自的差别还是很大的,工作侧重点甚至思维方式都不同。为了给刚入门的朋友介绍得清晰一些,这里就简单串一串我遇到的不同的算法。 算法与非算法的区别 一般来说,...

    作者: 龙心尘
    时间: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....
    • 遗传算法
      建立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()

    这里写图片描述

    展开全文
  • 做算法题的几个思路

    千次阅读 2012-08-10 14:36:44
    看到这类的难题不要慌,《算法设计与分析基础》一书比较全面地总结了做算法题目的一些思路: (1)蛮力穷举法,可以说可以解决所有的问题,不过对于组合数很大的问题时间性能不是很好甚至不能忍受。例子:全排列的...

    算法题目往往比较复杂,要么让人感到无从下手,要么很难给出一个最优解,但这恰恰是考验一个程序员思维方式的有效手段。看到这类的难题不要慌,《算法设计与分析基础》一书比较全面地总结了做算法题目的一些思路:

    (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的相关算法原理,其实用在敏感词汇过滤这块,主要还是前缀树的应用。 这个算法最原始的实现我是采用...

    在敏感词汇过滤这块,不同的算法所造成的性能差异是非常大的,选择一个合适的算法非常重要。因为以前做算法的时候做过类似前缀树的字符串匹配之类的算法,所以一开始就打算用前缀树做的,后面了解了一下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

    展开全文
  • LBP算法的Matlab代码

    万次阅读 多人点赞 2013-03-06 17:33:24
    说明:一共有三个m文件,一个是lbp.m, 存放主要的lbp算法,一个是getmapping,用以做算法的辅助函数,一个是lbptest.m,存放着测试代码。这三个文件需要放到同一个文件夹,并在文件夹中添加相应的图片,具体的图片名字...
  • 主宰操作系统的经典算法

    万次阅读 多人点赞 2020-07-24 15:22:50
    进程和线程在调度时候出现过很多算法,这些算法的设计背景是当一个计算机是多道程序设计系统时,会频繁的有很多进程或者线程来同时竞争 CPU 时间片。 那么如何选择合适的进程/线程运行是一项艺术。当两个或两个以上...
  • 有没有对算法非常了解的大神,小弟在学一个cocos2dx象棋游戏中使AI困难模式的算法使用alphaBetaSearch搜索算法,不过本人对这个算法的了解不是很深,整个游戏框架基本搭建完成,但是就算使用了减枝优化后,实际...
  • 通信算法工程师需要的那些事

    万次阅读 2018-05-23 21:46:17
    通信的算法可以基于仿真平台去验证和实现,是实现我们idea的理想地方。仿真平台可以基于很多工具搭建,比如matlab,python,C++等,由于matlab是美国MathWorks公司出品的商业数学软件,主要应用于工程计算、控制设计、...
  • 从最大似然到EM算法浅解

    万次阅读 多人点赞 2013-01-24 13:14:23
    从最大似然到EM算法浅解 ... 机器学习十大算法之一:EM算法。能评得上十大之一,让人听起来觉得挺NB的...神为什么是神,因为神能很多人不了的事。那么EM算法能解决什么问题呢?或者说EM算法是因为什么而来到这个世界
  • PID算法的解析

    万次阅读 多人点赞 2018-06-19 22:19:49
    LZ以前有个小小的理想,就是让手边的MCU自己“思考”起来,写出真正带算法的程序。 前段时间一个比赛项目的过程中,对经典、实用的PID算法有了一点点自己的理解,就写了这些,与大家分享 因为LZ想尽办法,试着用...
  • 前言 想象一下,当今社会备受瞩目的人工智能和数据挖掘算法工程师每天大部分时间都在什么呢?...机器学习界普遍认为:“数据和特征决定了机器学习算法的上限,而模型和算法只是不断逼近这个上限而已。” 在这场以模型
  • 总结的基础算法包括:估算算法和控制算法======================================1估算算法:•1.传感器驱动编写&amp;地面站上位机的使用 最基本的协议:UART、I2C,SPI、CAN… ...
  • 模拟退火算法--自己的ppt

    千次阅读 2016-08-28 08:59:33
    原文地址:模拟退火算法--自己的ppt作者:雪后DE阳光1、 模拟退火算法(起源) 模拟退火算法起源于物理退火。 􀂄物理退火过程: (1)  加温过程 (2)  等温过程 (3)  冷却过程     物理退火...
  • ELM算法多分类吗?谁有ELM多分类的matlab程序~
  • Android_基于G-Sensor的计步算法

    万次阅读 多人点赞 2015-04-25 19:39:29
    目前在计步领域比较领先的有乐动力以及春雨计步器,在做算法的参数调试的时候也是一直拿这两个应用做对比。 乐动力当之无愧行业第一,不管是应用的体验还是准确度都是非常棒,春雨计步器的亮点是轻量级,使用以及...
  • RANSAC算法做直线拟合

    千次阅读 2015-12-31 13:13:45
    RANSAC算法之前了解过相关的原理,这两天利用晚上闲暇的时间,看了一下RANSAC算法的Python代码实现,这方面的资料很多了,这里就不在重复。在分析该RANSAC.py代码之前,想用自己的对RANSAC的理解对其下总结。 ...
  • 动态规划中的 循环结构可以通过递归的方式实现,但是单纯的递归方法每次都会将已计算过的子问题重新计算,时间复杂度较高,因此可以通过在递归中备忘录的方法建设时间复杂度。具体见代码: #include using ...
  • #web互联网#下面我从程序的角度来和你分享关于算法工程师的那些事。提供第三方接口现在很多互联网企业都提供了各种各样的接口供第三方调用,这里面也涉及算法工程师的事情,比如...
  • 遗传算法中的转盘算法

    千次阅读 2012-09-02 13:07:18
    设前几天dirichlet process的时候看到了转盘算法,当时很不理解。 转盘算法是遗传算法中的,相当于一个selector,对不同的概率选择的程度不同,倾向于选择大概率事件。 前几天dirichlet process时候看到了...
  • Python-opencv3 SIFT算法做特征匹配

    万次阅读 热门讨论 2018-04-13 17:51:39
    这里面牵扯到了尺度不变而对特征变换的问题。这里简单介绍一下SIFT的概念,并知晓如何找到SIFT中的Keypoints和Descriptors,最后展示一个Demo。 简介 SIFT(Scale-invariant feature transform),也叫尺度...
  • 注意,此文不对算法的具体细节深究,仅供基础入门学习。限于篇幅原因,本文先介绍【对称加密算法】。 对称加密算法  对称加密算法,顾名思义,就是算法的执行过程是对称的;用最简单的话说,就是加密方和解密方...
  • 对于学习算法,个人的理解就是首先要去理解算法的本质,然后想想算法的实现过程,如何用代码去描述这个算法,然后就是去记模板了(对于像我这种初学者来说,这一步其实蛮重要的)。另外说下最短路问题的一些容易...
  • 迭代算法与递归算法的概念及区别

    万次阅读 2019-04-30 14:19:20
     利用迭代算法处理问题,需要做好以下三个方面的工:  一、确定迭代变量。在能够用迭代算法处理的问题中,至少具有一个间接或间接地不断由旧值递推出新值的变量,这个变量就是迭代变量。  二、建...
  • 算法的离线评估

    千次阅读 2017-11-04 17:32:10
    在平时项目的过程中,算法迭代是至关重要的,如果能准确找到算法的优化点和优化空间,那么可以使得最终的效果有很大的提升。 在实际的项目中,一个算法模块的上线可能会涉及算法,引擎,前段,测试等等一堆模块的...
  • 贪心算法与动态规划算法的异同

    千次阅读 2017-03-12 19:55:30
    今天比赛硬是把贪心成了背包问题,气哭口亨!动态规划和贪心算法都是一种递推算法,均由局部最优解来推导全局最优解 。渊博二转但是最后树的原创很精彩贪心算法: 不断贪心地选取当前最优策略的算法设计方法。 1...
  • 初级算法学习步骤

    千次阅读 多人点赞 2018-07-29 18:51:51
    前言 零散整理一个多月终于整理完了。...一直没时间吧之前的总结整理出来,现在准备整理一下用java做算法的一些东西……学习了两个月左右算法,从啥都不会到小白再到算是初级……做一个总结,请高手多多指...
  • 算法-动态规划 Dynamic Programming--从菜鸟到老鸟

    万次阅读 多人点赞 2017-07-15 22:58:29
    前言最近在牛客网上了几套公司的真题,发现有关动态规划(Dynamic Programming)算法的题目很多。相对于我来说,算法里面遇到的问题里面感觉最难的也就是动态规划(Dynamic Programming)算法了,于是花了好长时间...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 102,855
精华内容 41,142
关键字:

做算法的