0

同义词链是一系列密切相关的词，跨越两个锚点。例如，英文单词“black”和“white”可以连接为：

黑色-黑暗-晦涩-隐藏-隐藏-舒适-舒适-简单-纯白色

或者，这里是“真”和“假”：

真-只是=公平=美丽=漂亮-艺术-人工-假-假

我正在开发同义词库 iOS 应用程序，我也想显示同义词链。目标是从单词关系的加权图中返回一个链。我的来源是一个带有加权数据的非常大的词库，其中权重衡量单词之间的相似性。（例如，“outlaw”与“bandit”密切相关，但与“rogue”的关系更远。）我们的实际值范围从 0.001 到 ~50，但您可以假设任何权重范围。

您建议采用哪些优化策略来实现这一点，例如，在典型 iOS 设备上处理的 5 秒内？假设词库有 50 万个词条，每个词条有 20 个关联。我敢肯定，有大量关于这类问题的先前研究，我会很感激有关可能适用于此的指示。

我当前的算法涉及从开头和结尾的单词递归下降几级，然后寻找截取单词，但是对于数千个 sqlite（或 Realm）选择，这变得太慢了。

4

2 回答 2

2

既然您说您的来源是一个带有加权数据的大型词库，我假设如果您选择任何单词，您将在相似度图中对其后继词具有权重。当我给出任何示例时，我将始终使用以下顺序：

黑色-黑暗-晦涩-隐藏-隐藏-舒适-舒适-简单-纯白色

让我们将单词视为图上的一个节点，一个单词与另一个单词之间的每个相似关系都是该图上的一条路径。每个路径都以成本加权，这是您对源文件的权重。因此，找到从一个词到另一个词的路径的最佳解决方案是使用A*（A 星）路径查找。

我使用最小的“成本”从一个单词到它的后继为 1。你可以相应地调整它。首先，您需要使用一个好的启发式函数，因为这是一个贪心算法。这个启发式函数将返回两个单词之间的“贪婪”距离，任何单词。您必须尊重这样一个事实，即它返回的“距离”永远不会大于两个单词之间的实际距离。由于我不知道同义词库的任何单词之间的任何关系，因此我的启发式函数将始终返回最小成本 1。换句话说，它始终会说一个单词是与任何其他单词最相似的单词。例如，我的启发式函数告诉我'black'是'white'的最佳同义词。

如果可以，您必须调整启发式函数，以便它以更准确的距离做出响应，从而使算法运行得更快。我猜这就是棘手的部分。

您可以在我发送的 Wikipedia 文章中看到算法的伪代码。但这里是为了更快的解释：

function A*(start,goal)
    closedset := the empty set    -- The set of nodes already evaluated.
    openset := {start}    -- The set of tentative nodes to be evaluated, initially containing the start node
    came_from := the empty map    -- The map of navigated nodes.

    g_score[start] := 0    -- Cost from start along best known path.
    -- Estimated total cost from start to goal through y.
    f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal)

    while openset is not empty
        current := the node in openset having the lowest f_score[] value
        if current = goal
            return reconstruct_path(came_from, goal)

        remove current from openset
        add current to closedset
        for each neighbor in neighbor_nodes(current)
            if neighbor in closedset
                continue
            tentative_g_score := g_score[current] + dist_between(current,neighbor)

            if neighbor not in openset or tentative_g_score < g_score[neighbor] 
                came_from[neighbor] := current
                g_score[neighbor] := tentative_g_score
                f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)
                if neighbor not in openset
                    add neighbor to openset

    return failure

function reconstruct_path(came_from,current)
    total_path := [current]
    while current in came_from:
        current := came_from[current]
        total_path.append(current)
    return total_path

现在，对于算法，您将拥有 2 个节点数组，您将要访问的节点（打开）和已经访问的节点（关闭）。对于每个节点，您还将有两个距离数组，您将在遍历图表时完成这些距离。

一个数组 ( g_score ) 将告诉您起始节点和指定节点之间的实际最低行进距离。例如，g_score["hidden"]将返回从'black'到'hidden'的最低加权成本。

另一个数组 ( f_score ) 将告诉您指定的节点与您想要达到的目标之间的假定距离。例如， f_score["snug"] 将使用启发式函数返回从“snug”到“white”的假定加权成本。请记住，这个成本总是小于或等于单词之间的实际成本，因为我们的启发式函数需要遵守上述规则。

随着算法的运行，您将从一个节点到另一个节点，从起始词开始，保存您经过的所有节点以及您“用于”旅行的成本。当您在g_score数组上找到更好的行驶成本时，您将替换已行驶的路径。您将使用f_score从“未访问”节点的数组中预测哪个节点最先被访问。最好将f_score保存为最小 Heap。

当您找到您想要的目标节点时，您将结束算法。然后，您将使用您在每次迭代中保存的访问过的节点数组重建最小路径。算法停止的另一种方式是，如果它访问了所有邻居节点并且没有找到目标。发生这种情况时，您可以说从起始节点到目标没有路径。

该算法最常用于游戏中，用于在 3D 世界中找到两个对象之间的更好路径。要改进它，你只需要创建一个更好的启发式函数，它可以让算法找到更好的节点先行，从而更快地到达目标。

-- 7f

于 2015-06-29T23:25:07.033 回答
1

这是一个密切相关的问题和答案：Algorithm to find multiple short paths

在那里您可以看到关于 Dijkstra 和 A-star、Dinic 的评论，但更广泛地也可以看到最大流量和最小成本流量的概念。

于 2021-03-09T19:04:12.207 回答