database - akinator 使用数据库运行？

Question

Akinator可以找到一切。我可以猜到 akinator 的算法，但我不明白，akinator 使用数据库或任何搜索引擎，因为找到一切。如果使用数据库，数据库的逻辑是什么？创始人如何找到所有知识？

现在就足够了:)

Answer 1

我将在这里进行推测，但不确定，因为我不是编写这个神奇机器人的人之一。

我想它一开始并没有现在那么聪明，但请记住：每次它得到一个错误的答案时，它都会要求您提出另一个问题，以区分 Akinator 的建议与您想到的实际人。因此，它建立在自己的知识库之上。

我想 Akinator 使用决策树，甚至C4.5 算法来选择每次查询的内容。它根据之前的答案提出问题，这更接近于 C4.5 算法，而不是经典的决策树。Akinator 真正令人惊奇的是，它甚至可以猜出你在一个甚至两个答案中犯错的一些情况。我想，这是机器人作者开发的算法的附加组件。

只需计算它是否包含数十万个问题，并且每个问题都有 5 个可能的答案，它可以猜出多少种不同的性格。

Answer 2

我不知道 Akinator 的原始算法究竟是如何实现的，但我们已经使用数据库解决了类似的任务。您可以在https://github.com/nesterovsky-bros/KB了解它的实现。

编辑：

建议的解决方案是一种算法，它将带有答案的问题列表作为输入，并提供下一个问题。该问题及其答案被添加到问题和答案集中。当没有更多问题时，实体列表由一组问题确定，这些问题具有这些问题的答案。

本质上，SQL 解决方案是这样工作的：

1. 定义表：

表“实体”定义对象：

create table Data.Entity
(
  EntityID int not null primary key, -- Object key.
  Name nvarchar(256) -- Object name
);

表“PredicateType”定义了问题类型：

create table Data.PredicateType
(
  PredicateID int not null primary key, -- question id
  Name nvarchar(128) not null unique -- question name.
);

表“谓词”存储谓词为真的实体：

create table Data.Predicate
(
  PredicateID int not null,
  EntityID int not null,
  constraint PK_Predicate primary key clustered(PredicateID, EntityID),
  constraint IX_Predicate_Entity unique(EntityID, PredicateID)
);

2. 解决方案是为一组输入问题和答案构建一个选择，在输出上提供一个新问题。

例如，如果我们有 P(i) - 问题，A(i) - 答案，i = 1..5，并且
A(1) = A(3) = 1，A(2) = A(4) = A(5) = 0 那么选择将如下所示：

  with P1 as -- P(1), A(1) = 1
  (
    select EntityID from Data.Predicate where PredicateID = @p1
  ),
  P2 as -- P(2), A(2) = 0
  (
    select EntityID from Data.Predicate where PredicateID = @p2
  ),
  P3 as -- P(3), A(3) = 1
  (
    select EntityID from Data.Predicate where PredicateID = @p3
  ),
  P4 as -- P(4), A(4) = 0
  (
    select EntityID from Data.Predicate where PredicateID = @p4
  ),
  P5 as -- P(5), A(5) = 0
  (
    select EntityID from Data.Predicate where PredicateID = @p5
  ),
  M as
  (
    select EntityID from Data.Entity
    intersect
    select EntityID from P1
    intersect
    select EntityID from P3
    except
    select EntityID from P2
    except
    select EntityID from P4
    except
    select EntityID from P5
  ),
  P as
  (
    select
      P.PredicateID,
      count(*) EntityCount,
      (select count(*) from M) TotalCount
    from
      Data.Predicate P
      inner join
      M
      on
        P.EntityID = M.EntityID
    where
      P.PredicateID not in (@p1, @p2, @p3, @p4, @p5)
    group by
      P.PredicateID
  )
  select top(5) PredicateID from P order by abs(TotalCount - EntityCount  * 2);

返回的结果集最好是下一个最佳谓词。

Answer 3

Akinator 是一个非常接近搜索引擎的东西。我认为数据库的可扩展性不足以实现 Akinator 之类的东西（至少：不是标准的类似 SQL 的关系数据库）。如果我尝试实现 Akinator，我会改用发布列表、倒排索引和类似的数据结构。