跳至主要内容

How to Implement String Case Insensitive Compare?

How to Implement String Case Insensitive Compare?

How would you implement a String Comparator used in String#compareToIgnoreCase? I may convert all character to upper case then compare like the following does:

int n1 = s1.length();
int n2 = s2.length();
int min = Math.min(n1, n2);
for (int i = 0; i < min; i++) {
    char c1 = Character.toUpperCase(s1.charAt(i));
    char c2 = Character.toUpperCase(s2.charAt(i));
    if (c1 != c2) {
       return c1 - c2;
    }
}
return n1 - n2;

It seems work and we may also use toLowerCase to replace toUpperCase. But the implementation in JDK source code doesn’t agree:

int n1 = s1.length();
int n2 = s2.length();
int min = Math.min(n1, n2);
for (int i = 0; i < min; i++) {
    char c1 = s1.charAt(i);
    char c2 = s2.charAt(i);
    if (c1 != c2) {
        c1 = Character.toUpperCase(c1);
        c2 = Character.toUpperCase(c2);
        if (c1 != c2) {
            c1 = Character.toLowerCase(c1);
            c2 = Character.toLowerCase(c2);
            if (c1 != c2) {
                // No overflow because of numeric promotion
                return c1 - c2;
            }
        }
    }
}
return n1 - n2;

Yes, it first convert it to upper case, then to lower case again! The logic seems to say that there exists some character that:

  • They have different upper case, but same lower case: so the second conversion is necessary to tell the difference;
  • They have different lower case, but same upper case: so the first conversion is necessary;

Feel confused about this logic, I am decided to find some examples to verify it. First I try to find in the JDK source code, which contains the mapping between lower case and upper case. But find a same one using eyes is too hard, so I write a simple program to find:

int charLimit = 65536;
for (int i = 0; i < charLimit; i++) {
  for (int j = i+1; j < charLimit; j++) {
    if (Character.toUpperCase(i) == Character.toUpperCase(j)
        && Character.toLowerCase(i) != Character.toLowerCase(j)) {
      System.out.format("same upper case: %c(%d) & %c(%d)\n", ((char) i), i, ((char) j), j);
    }
    if (Character.toLowerCase(i) == Character.toLowerCase(j)
        && Character.toUpperCase(i) != Character.toUpperCase(j)) {
      System.out.format("same lower case: %c(%d) & %c(%d)\n", ((char) i), i, ((char) j), j);
    }
  }
}

And I indeed find some examples:

same lower case: I(73) & İ(304)
same upper case: I(73) & ı(305)
same lower case: K(75) & K(8490)
same upper case: S(83) & ſ(383)

After some searching, I found this is related to different locales, as Infamous turkish locale bug introduced. It says in the Turkish Locale, the uppercase counterpart of i is not I, but İ. And in return, the I is not transformed to i, but a “dotless i”: ı. Showing in illustration can be the following:

i   ı     
|\  |
| \ |
|  \|
İ   I

So comparing a string is not so easy as we have thought. In the real wold, even such a simple task can be wrong. Actually, compare of locate related string should avoid using String#compareIgnoreCase, as the document of this comparator says:

Note that this method does not take locale into account, and will result in an unsatisfactory ordering for certain locales. The java.text package provides collators to allow locale-sensitive ordering.

And the following is the recommended way to compare string in real application:

//Get the Collator for US English and set its strength to PRIMARY
Collator usCollator = Collator.getInstance(Locale.US);
usCollator.setStrength(Collator.PRIMARY);
if( usCollator.compare("abc", "ABC") == 0 ) {
    System.out.println("Strings are equivalent");
}

For comparing Strings exactly once, the compare method provides the best performance. When sorting a list of Strings however, it is generally necessary to compare each String multiple times. In this case, CollationKeys provide better performance. The CollationKey class converts a String to a series of bits that can be compared bitwise against other CollationKeys. A CollationKey is created by a Collator object for a given String.

Ref

Written with StackEdit.

标签：

评论

发表评论

此博客中的热门博文

Spring Boot: Customize Environment

Spring Boot: Customize Environment Environment variable is a very commonly used feature in daily programming: used in init script used in startup configuration used by logging etc In Spring Boot, all environment variables are a part of properties in Spring context and managed by Environment abstraction. Because Spring Boot can handle the parse of configuration files, when we want to implement a project which uses yml file as a separate config file, we choose the Spring Boot. The following is the problems we met when we implementing the parse of yml file and it is recorded for future reader. Bind to Class Property values can be injected directly into your beans using the @Value annotation, accessed via Spring’s Environment abstraction or bound to structured objects via @ConfigurationProperties. As the document says, there exists three ways to access properties in *.properties or *.yml : @Value : access single value Environment : can access multi...
5 条评论
阅读全文

LevelDB Source Reading (4): Concurrent Access

In this thread, we come to the issue of concurrent access of LevelDB. As a database, it can be concurrently accessed by users. But, it wouldn’t be easy to provide high throughput under product load. What effort does LevelDB make to achieve this goal both in design and implementation? Goal of Design From this github issue , we can see LevelDB is designed for not allowing multi-process access. this (supporting multiple processes) doesn’t seem like a good feature for LevelDB to implement. They believe let multiple process running would be impossible to share memory/buffer/cache, which may affect the performance of LevelDB. In the case of multiple read-only readers without altering the code base, you could simply copy the file for each reader. Yes, it will be inefficient (though not on file systems that dedupe data), but then again, so would having multiple leveldb processes running as they wouldn’t be able to share their memory/buffer/etc. They achieve it by adding a l...
发表评论
阅读全文

LevelDB Source Reading (3): Compaction

LevelDB Source Reading (3): Compaction In the last blog that analyzes read/write process of Leveldb, we can see writing only happens to log file and memory table, then it relies on the compaction process to move the new updates into persistent sorted table for future use. So the compaction is a crucial part for the design, and we will dive into it in this blog. Compaction LevelDB compacts its underlying storage data in the background to improve read performance. The upper sentence is cited from the document of Leveldb , and we will see how it is implemented via code review. Background compaction // db_impl.cc void DBImpl :: MaybeScheduleCompaction ( ) { // use background thread to run compaction env_ - > Schedule ( & DBImpl :: BGWork , this ) ; } Two main aspects // arrange background compaction when Get, Open, Write void DBImpl :: BackgroundCompaction ( ) { // compact memtable CompactMemTable ( ) ; // compact ...
发表评论
阅读全文