上传代码；

chr

2026-04-05 fe750b791d5b517cc4e9bc8e99a9a75139a0cfba

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
using System;
using System.Text;
 
namespace OpenTap.Package
{
    internal class FuzzyMatcher
    {
        public class Match
        {
            public Match(string candidate, int score)
            {
                Candidate = candidate;
                Score = score;
            }
            public string Candidate { get; set; }
            public int Score { get; set; }
            public override string ToString()
            {
                return $"{Candidate}: {Score}";
            }
        }
        public string Input { get; }
 
        public FuzzyMatcher(string input, int maxThreshhold)
        {
            Input = preprocess(input);
            _maxThreshhold = maxThreshhold;
        }
 
        /// <summary>
        /// Remove all punctuation and whitespace from the input, and lowercase it
        /// </summary>
        /// <param name="str"></param>
        /// <returns></returns>
        private string preprocess(string str)
        {
            var sb = new StringBuilder(str.Length);
            foreach (var ch in str)
            {
                if (char.IsLetterOrDigit(ch))
                    sb.Append(ch);
            }
 
            return sb.ToString().ToLower();
        }
 
        // Only consider candidates that are within an edit distance of 3 from the input
        // E.g. the input string can be transformed to the candidate with 3 changes (adding, removing, or replacing a character)
        private int _maxThreshhold;
        private int LevensteinDistance(string candidateString, string inputString, int x, int y, int score)
        {
            if (score > _maxThreshhold) return score;
            if (x == candidateString.Length) return score + inputString.Length - y;
            if (y == inputString.Length) return score + candidateString.Length - x;
            if (candidateString[x] == inputString[y]) return LevensteinDistance(candidateString, inputString, x + 1, y + 1, score);
            return Math.Min(
                LevensteinDistance(candidateString, inputString, x, y + 1, score + 1), // insert
                Math.Min(
                    LevensteinDistance(candidateString, inputString, x + 1, y, score + 1), // remove
                    LevensteinDistance(candidateString, inputString, x + 1, y + 1, score + 1))); // replace
        }
 
        /// <summary>
        /// Calculate how similar a candidate is to the input
        /// </summary>
        /// <param name="candidate"></param>
        /// <returns></returns>
        public Match Score(string candidate)
        {
            var score = 0;
            if (string.IsNullOrWhiteSpace(candidate)) return new Match(candidate, 0);
            var prep = preprocess(candidate);
 
            if (prep.Contains(Input))
            {
                if (prep == Input)
                    return new Match(candidate, 0);
                // If the input is a prefix of the package name, it is considered a very good candidate
                if (prep.StartsWith(Input) || prep.EndsWith(Input))
                    return new Match(candidate, 1);
                // If the input is a substring of the package name, it is a pretty good candiate
                return new Match(candidate, 2);
            }
            // If the candidate is a substring of the input, it is still worth considering if there are no better options.
            else if (Input.Contains(prep))
            {
                return new Match(candidate, 3);
            }
 
            // Otherwise, the suitability is determined by the edit distance
            // E.g. how many modifications do we need to make to the candidate to turn it into the input
            score = LevensteinDistance(prep, Input, 0, 0, 0);
            return new Match(candidate, score);
        }
    }
}