.net - 使用 .NET 实现全文搜索的理想功能语言

Question

就目前而言，这个问题不适合我们的问答形式。我们希望答案得到事实、引用或专业知识的支持，但这个问题可能会引起辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开，visit the help center为指导。




8年前关闭。




在我学习计算机科学的过程中，我接触了一些函数式语言，比如 Prolog，但现在我在过去 10 年里只做命令式的东西，比如 C#、Ruby JavaScript 和 Java。目前，我正在为一家在线商店创建一个全文搜索引擎，而且我已经走得很远了。但是在偶然接触了一些函数式语言(如 Clojure 的 Haskell)之后，很明显函数式范式更适合，而且命令式方法并不是完成这项工作的正确工具。

所以我们有大约 1000 万条记录的全文索引。每条记录基本上都包含一个单词出现，以及它源自的记录的 id 和文本位置。

当用户输入搜索字符串时，它会被解析为表达式树。例如，搜索字符串“transformer 100 W”的结果类似于

AND('transformer%', OR(NEAR('100', 'W'), NEAR('100', 'watts'), '100W', '0.1kW'))

这里有一些额外的“智能”，但这与这个问题无关。

然后对表达式树进行递归评估，并生成几个 sql 查询，这些查询可能以 .NET-DataTables 的形式返回多达 100,000 行。然后将它们读入集合或字典，并根据谓词应用交集和并集，以找到与整个搜索表达式匹配的所有结果。对于 NEAR 评估，还比较了所发现事件的位置索引。但这一切都是命令式完成的，有很多 for 循环。

此外，还有一个排名功能，可以将找到的单词出现的分数相加。仅作为前缀或模糊匹配(由数据库服务器完成)找到的单词的得分低于精确匹配。

对于每个结果项目，我还需要获取所有匹配的单词出现的列表，以便在结果页面中突出显示这些单词。

所以粗略的评估算法是一个函数

expression tree, full text index -> 
resulting items that match the expressin tree, 
each with a ranking sum 
and a list of all found word occurrences for this item

我只是在这里给出一个粗略的概述，但我希望你得到足够的图片。

现在“现实世界”的约束:

整个应用程序(到目前为止)都是用 C# 编写的，因此与 .NET 的轻松集成至关重要。

大量数据被读入 .NET-DataTables，然后需要进行评估和转换。结果应包含在 .NET 类型(字典、集合、数组，等等)中。

性能非常重要。目前我的算法搜索通常需要两秒钟(不包括sql)，这还可以，但应该改进。我们的服务器有 16 个处理器，因此欢迎并行处理。由于我们每秒收到大约一个搜索请求，并且当前的实现是单线程的，因此处理器时间仍然可用。

语言(和编译器)应该是成熟的。

由于我需要继续使用 .NET，我正在研究用于 .NET 的 Clojure-CLR、F# 和 Scala。

我非常喜欢 Clojure 的概念，但现在我无法评估它是否适合这份工作。阅读 F# 给我带来了复杂的感觉，因为它似乎希望能够做几乎所有的事情，而我倾向于对给定的任务采用更“纯”的数学方法。但也许这对 F# 也是可能的，我还没有意识到这一点。我还没有深入研究 Scala，但它似乎已经很成熟了。

欢迎任何见解!

Answer 1

• The whole application (up to now) is written in C#, so an easy integration with .NET is paramount.
• Loads of data is read into .NET-DataTables and will then need to be evaluated and transformed. The results should be contained in .NET types (Dictionaries, Sets, Arrays, whatever...).

F# 应该是一个更好的选择。作为 Visual Studio 中的一流语言，F# 与 C# 的互操作性非常好。

• Performance is of great importance. At present my algorithm often takes two seconds for a search (not counting the sql), which is kind of ok, but should be improved. Our server has 16 processors, so parallel processing would be welcome. Since we get about one search request per second and the current implementation is single threaded, processor time is still available.

假设您从功能优先且不可变的实现开始，那么并行化您的应用程序应该很容易。此外， asynchronous workflow对于像您这样的 IO 绑定(bind)应用程序来说是一种祝福。

• The language (and the compiler) should be mature.

我不会将 F# 与 JVM 上的 Clojure 和 Scala 进行比较，但 F# 比 .NET 上的 Clojure CLR 和 Scala 成熟得多。在选择 F# 时，您肯定会得到 Microsoft 的长期 promise 和不断增长的 F# 社区的帮助。

When the user enters a search string it is parsed into an expression tree.

您可以使用 discriminated unions 表示表达式树.随着 query expressions的介绍在 F# 3.0 中，您可以轻松地将逻辑转换为 SQL 查询。您甚至可以通过为您的域定义类似的查询语言来进一步插入它。

Reading about F# gave me mixed feelings, since it seems to want to be able to do just about everything, whereas I would tend to a more "pure" mathematical approach for the given task. But maybe that is possible with F# as well and I am not yet aware of it.

F# 3.0 引入 type providers允许用户以类型安全的方式访问非结构化数据；你可能想看看 this "F# 3.0 - Information Rich Programming" video了解更多信息。如果你想使用 F# 作为数据挖掘的编程语言，我已经问了一个相关的问题并且得到了很好的回答 here .

也就是说，您对 F# 的第一感觉可能不正确。根据我的经验，您可以随时随心所欲地接近功能性和不可变的一面。鉴于您已经有一个有趣的应用程序，我建议您亲自动手，了解 F# 是否适合您的目的。

更新:

这是一个 F# 原型(prototype)，它演示了这个想法:

/// You start by modeling your domain with a set of types.
/// FullText is a sequence of Records, which is processed on demand.
type Word = string
and Freq = int
and Record = {Occurrences: (Word * Freq) list; Id: string}
and FullText = Record seq

/// Model your expression tree by following the grammar closely.
type Expression =
    | Occur of Word
    | Near of Word * Word
    | And of Expression * Expression 
    | Or of Expression * Expression

/// Find wether a word w occurs in the occurrence list.
let occur w {Occurrences = xs} = xs |> Seq.map fst |> Seq.exists ((=) w)

/// Check whether two words are near each other.
/// Note that type annotation is only needed for the stub implementation.
let near (w1: Word) (w2: Word) (r: Record): bool = failwith "Not implemented yet"

/// Evaluate an expression tree.
/// The code is succinct and clear thanks to pattern matching. 
let rec eval expr r = 
    match expr with
    | Occur w -> occur w r
    | Near(w1, w2) -> near w1 w2 r
    | And(e1, e2) -> eval e1 r && eval e2 r
    | Or(e1, e2) -> eval e1 r || eval e2 r

/// Utility function which returns second element in a 3-tuple
let inline snd3 (_, x, _) = x

/// Get the rank of the record by adding up frequencies on the whole database.
let rank (r: Record) (ft: FullText): Freq = failwith "Not implemented yet"

/// Retrieve all records which match the expression tree.
let retrieve expr fullText =
    fullText |> Seq.filter (eval expr)
             |> Seq.map (fun r -> r, rank r fullText, r.Occurrences)
             |> Seq.sortBy snd3

/// An example query
let query = 
    And (Occur "transformer%", 
         Or (Or (Near ("100", "W"), Near ("100", "watts")), 
             Or (Occur "100W", Occur "0.1kW")))