使用.NET实现全文搜索的理想函数语言

在我学习计算机科学的过程中,我遇到了一些像Prolog这样的函数式语言,但是现在我在过去10年里只做过像C#, Ruby JavaScript和Java等强制性的东西.目前我正在为网上商店创建一个全文搜索引擎,我已经走到了“必要的方式”.但是,遇到像Caskjure的Haskell这样的函数式语言时,很明显功能范式非常合适,并且命令式方法不适合这项工作.

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

当用户输入搜索字符串时,它将被解析为表达式树.例如,搜索字符串“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,我正在研究Clojure-CLR,F#和Scala for .NET.

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

任何见解都会受到欢迎！

我很好奇为什么你不考虑LINQ作为选项.它似乎满足您的所有标准.注意我没有使用Scala的经验,因此我无法对此发表评论.

• 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…).

这里,LINQ> F#> Clojure的-CLR.如果一切都已经在C#中,LINQ将是最容易集成的.在C#-only程序中,Visual Studio对智能感知和函数定义导航等功能的支持似乎要好得多.从C#调用Clojure可能是可怕的 – 理论上它应该可以正常工作,但在实践中,要准备好花几周的时间来弄清楚为什么事情没有按照你期望的方式运行.它真的被设计成顶级的东西;你从Clojure调用C#,反过来说Clojure-CLR开发人员的优先级列表并不高;有基本的支持,但你得到你得到的.

• 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.

LINQ~ = F#> Clojure的.我在其他地方读过,对于大多数惯用语编写的算法,LINQ的性能可以比F#略好,但是它们足够接近它应该无关紧要. PLINQ使并行性变得容易. Clojure-CLR的启动时间非常慢,而且运行时开销也会降低速度.

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

LINQ> = F#> Clojure的.不是说F#根本不成熟,但是Visual Studio支持有点滞后,而且基于LINQ而不是F#,世界上有更多的生产代码(以及更多的堆栈溢出答案).

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.

没有一种语言像Haskell那样纯粹纯粹,但就编写非纯代码的难度而言,我将其排列为：LINQ> Clojure> F#>斯卡拉.只能通过调用不纯的方法使LINQ变得不纯洁. Clojure有refs和atoms,F#任何东西都可以指定为mutable,而Scala(根据我的理解)实际上只是带有功能特性的Java.

F#和Scala都具备的功能特性是模式匹配的语言支持.在C#中,您需要某种继承层次结构或b？x：y运算符链以在功能上执行操作(或者如果/如果您对非功能方法很好),模式匹配会在不同的情况下进行条件运算原始数据类型的变化更加简洁.这可能对你计算精确vs前缀vs模糊匹配排名很有用,但是b？x：y chain var alg = x.match == exact？ alg1：x.match ==前缀？ alg2：在这个简单的情况下,C#中的alg3将非常清晰 – 当匹配变得更加复杂时,语言集成模式匹配变得更有价值.

有趣的是,我认为你的工具包的一个方面,即F#比LINQ更有用,不是查询,LINQ本身的名称应该表明它可以处理,而是将搜索字符串解析为表达式树.这是函数式语言和模式匹配真正优秀的一个领域,而像FsLex和FsYacc这样的工具可以为您提供一个很好的开端.

所有这一切,我认为决定归结为你想去的地方.如果您只是想清理搜索算法并完成它,我会建议使用LINQ方法.但是,如果你想要逐个进入一个更加功能导向的整个程序风格(并且你的公司愿意支付你承诺的时间),那么可以看看F#选项.无论哪种方式,我都会首先使用LINQ选项,因为这对您来说可能更为直接,并且一旦您开始沿着这条路走下去,就可以帮助指导您的F#更具功能性.

简单地说,这就是你想要的,只需填写你的Near和Equal fetchers的函数,以及你的GetRank和GetStrings函数,并使用下面的代码

static IEnumerable<Record> FetchRecords(this Tree tree) {
    return tree.Op == "OR"    ? tree.Args.SelectMany(FetchRecords).Distinct() :
           tree.Op == "AND"   ? tree.Args.Select(FetchRecords).Aggregate((intersect, current) => intersect.Intersect(current)) :
           tree.Op == "NEAR"  ? FetchValsNear(tree.Args[0].Op, tree.Args[1].Op) :
                                FetchValsEqual(tree.Op);
}

static IEnumerable<Record> FetchValsEqual(string s) {
    throw new NotImplementedException();
}

static IEnumerable<Record> FetchValsNear(string s1, string s2) {
    throw new NotImplementedException();
}

static IEnumerable<Tuple<Record, double, string[]>> OrderByRank(this IEnumerable<Record> vals) {
    return from val in vals
           let rank = GetRank(val)
           orderby rank
           let strings = GetStringsIn(val)
           select Tuple.Create(val, rank, strings);
}

static string[] GetStringsIn(Record val) {
    throw new NotImplementedException();
}

static double GetRank(Record val) {
    throw new NotImplementedException();
}

class Tree {
    public string Op;
    public Tree[] Args;
}

struct Record {/*your record here--use struct so Distinct and Intersect above work naturally (or use class and override Equals)*/}

像这样：

foreach (var tuple in myTree.FetchRecords().AsParallel().OrderByRank().Take(30)) {
    // add to datagrid or whatever
}

这为您提供了简单的可并行性和懒惰性,因此GetStringsIn函数仅对您拍摄的记录执行(在本例中为前30个). (注意,可以使用任何IntersectAll示例here简化AND选择器).