13

我可能正在考虑这个错误，但这里有。

计算机开始在线性行中吐出 11111111111111111111 和 999999999999999999999 之间的无数随机数：

  • 有时计算机会在一行的一端添加一个数字。
  • 有时计算机会在线路的另一端添加一个数字。
  • 每个数字都有一个之前出现或将要出现的数字。
  • 每个数字都有一个后面出现或将要出现的数字。
  • 并非所有数字都是唯一的，许多数字（但不是大多数数字）是重复的。
  • 计算机永远不会停止吐出数字。

当我记录所有这些数字时，我需要能够在任何给定时间做出有根据的猜测：

  • 如果这是我第二次看到一个数字，我必须知道上次排在它前面的数字是什么。

  • 如果它出现了两次以上，我必须知道它前面的数字的概率/频率。

  • 如果这是我第二次看到一个数字，我一定也知道上次排在它后面的是什么数字。

  • 如果它出现了两次以上，我必须知道它后面出现的数字的概率/频率。

我到底如何在 MySQL 数据库中构建表来存储所有这些数字？我使用哪个引擎，为什么？如何制定我的查询？我需要快速知道，但容量也很重要，因为什么时候才能停止吐出它们？

我的拙劣计划：

2 表：

1. Unique ID/#
2. #/ID/#

我的想法：

唯一 ID 几乎总是比数字短=更快的匹配。数字重复 = 更少的 ID 行 = 最初的匹配速度更快。

Select * in table2 where id=(select id in table1 where #=?)

或者：

3 表：

1. Unique ID/#
2. #/ID
3. ID/#

我的想法：

如果我只需要左/前，或者只需要后/右，我会缩小第二个查询的大小。

SELECT # IN table2(or 3) WHERE id=(SELECT id IN table1 WHERE #=?)

或者

1 表：

1. #/#/#

想法：

更少的查询=更少的时间。

SELECT * IN table WHERE col2=#.

我迷路了.... :(每个数字都有四个属性，一个是前面+频率，一个是后面+频率。

我这样想会更好吗？如果我在表中存储和增加频率，我会消除重复从而加快我的查询速度吗？我最初在想，如果我存储每一个事件，以编程方式计算频率会更快......

如此简单的数据，但我只是不知道数据库如何运行以知道哪个更有效。

根据最近的评论，我想添加一些关于实际问题的信息：我有一个不定长度的字符串。我正在尝试在此字符串中存储各种字符或字符块的马尔可夫链频率表。

给定字符串中的任何点，我需要知道下一个状态的概率和前一个状态的概率。

我正在预测用户输入，基于文本语料库和过去的用户输入。与我见过的其他应用程序相比，一个主要的区别是我在给定的时间走得更远，更多的状态，我需要频率数据来提供多种可能性。

我希望这能更清楚地说明情况。我不想深入了解问题的本质，因为过去我创建的问题不够具体，无法得到具体的答案。

这似乎可能好一点。我对这个解决方案的主要问题是：提供“密钥”（状态的前几个字符）会提高系统的速度吗？即查询state_key，然后只查询该查询的结果以获得完整状态？

Table 1:
name: state
col1:state_id - unique, auto incrementing
col2:state_key - the first X characters of the state
col3:state - fixed length string or state

Table 2:
name: occurence
col1:state_id_left - non unique key from table 1
col2:state_id_right - non unique key from table 1
col3:frequency - int, incremented every time the two states occur next to each other.

QUERY TO FIND PREVIOUS STATES:
SELECT * IN occurence WHERE state_id_right=(SELECT state_id IN state WHERE state_key=? AND state=?)

QUERY TO FIND NEXT STATES:
SELECT * IN occurence WHERE state_id_left=(SELECT state_id IN state WHERE state_key=? AND state=?)
4

2 回答 2

2

我不熟悉马尔可夫链，但这里试图回答这个问题。注意：为简化起见，我们将每个数字字符串称为“状态”。

首先我想象这样一张桌子

Table states:
order : integer autonumeric (add an index here)
state_id : integer (add an index here)
state : varchar (?)

order：只需使用序列号 (1,2,3,...,n)，这样可以轻松搜索上一个或下一个状态。

state_id：与状态关联的唯一编号。例如，您可以使用数字 1 来表示状态“1111111111...1”（无论序列的长度是多少）。重要的是状态的再次出现需要使用与之前使用的相同的 state_id。您可以根据字符串（可能减去一个数字）来制定 state_id。当然，state_id 只有在可能的状态数适合 MySQL int 字段时才有意义。

状态：那是数字'11111111...1'到'99999999...9'的字符串......我猜这只能存储为字符串，但如果它适合整数/数字列，你应该试试看，因为很可能你不需要 state_id

state_id 的重点是搜索数字比搜索文本更快，但在性能方面总是需要权衡取舍......配置文件并确定您的瓶颈以做出更好的设计决策。

那么，您如何查找先前出现的状态 S_i ？

“SELECT order, state_id, state FROM states WHERE state_id =” 然后附加 get_state_id(S_i) 其中 get_state_id 理想情况下使用公式为状态生成唯一 id。

现在，使用 order - 1 或 order + 1，您可以访问发出附加查询的相邻州。

接下来我们需要跟踪不同发生的频率。您可以在可能如下所示的不同表中执行此操作：

Table state_frequencies:
state_id integer (indexed)
occurrences integer

并且仅在获得数字时添加记录。

最后，您可以使用表格来跟踪相邻州的频率：

Table prev_state_frequencies (next_state_frequencies is the same):
state_id: integer (indexed)
prev_state_id: integer (indexed)
occurrences: integer

您将能够通过查看状态的出现次数（在 state_frequencies 中）与其前一状态的出现次数（在 prev_state_frequencies 中）来推断概率（我猜这是您想要做的）。

我不确定我是否解决了您的问题，但如果这是有道理的，我猜我有。

希望对你有帮助啊

于 2012-12-23T05:27:30.297 回答
1

在我看来，马尔可夫链是有限的，所以首先我会从定义链的限制开始（即 26 个字符，需要填充 x 个空格），然后您可以计算可能组合的总数。确定某种字符排列的概率，如果我没记错的话，数学是：


x = ((C)(C))(P)
其中
C = 可能的字符数，
P = 总潜在结果。

这是要存储的大量数据，而创建过滤数据的程序可能会变成一项看似无止境的任务。

-> 如果您在表中使用自动递增的 id，您可以查询该表并使用 preg_match 对照以前的结果测试新结果，然后将新结果的总匹配数插入表中，这也允许您查询前面的结果以查看之前的结果，这应该让您大致了解结果中的模式以及统计相关性和新算法生成的一般基础

于 2012-12-23T04:44:59.790 回答