誰もこの正規表現アルゴリズムのより高速な代替案を提案することができますか？

Question

私はこの関数をかなり頻繁に呼び出す必要があります。基本的にはアクセント付きの文字をアクセントのない同等のものに置き換え、スペースを "_"に変更して小文字に変換し、残りのエイリアンコードを取り除くので、ファイル名/ URLパス/などとしても安全です。あなたが見ているように、それはパフォーマンスの観点からひどく見えます。誰もよりクリーンで高速な代替手段を考えることができますか？

• ケース1）それがここに掲載されて元のルーチン：

  public static String makeValidPathName(String rawString) { 
      if (rawString==null) return null; 
      rawString = rawString.replaceAll("[ÁÀÂÄáàäaàáâãäå]","a"); 
      rawString = rawString.replaceAll("æ","ae"); 
      rawString = rawString.replaceAll("çÇ","c"); 
      rawString = rawString.replaceAll("[ÈÉÊËèéêë]","e"); 
      rawString = rawString.replaceAll("[ìíîïÍÌÎÏ]","i"); 
      rawString = rawString.replaceAll("ñÑ","n");        
      rawString = rawString.replaceAll("[ÓÓÖÔòóôõö]","o"); 
      rawString = rawString.replaceAll("œ","oe"); 
      rawString = rawString.replaceAll("[ÙÚÛÜùúûü]", "u"); 
      rawString = rawString.replaceAll("[ýÿ]","y"); 
      rawString= rawString.replaceAll("[^a-z A-Z 0-9 \\_ \\+]",""); 
      rawString = rawString.replaceAll(" ","_"); 
      return rawString.toLowerCase(); 
  } 
  

  --- EDIT

  [OK]を、みんな...私はすべての4例の性能試験を行いました。

• ケース2）
• ケース3）

@Erik Pragtによって示唆SparseArray

ケース4）ノーマアプローチのための私の最適化を@devconsoleによって示唆ルックアップテーブルを@WCharginによって示唆改善そして...勝者はそれが最適化がHELないパターンのコンパイルを面白い... TADAAA .....

D/REPLACEMENT_TEST(18563): *** Running Tests (1000 iterations) 
D/REPLACEMENT_TEST(18563): Original REGEX : 13533 ms 
D/REPLACEMENT_TEST(18563): Compiled REGEX : 12563 ms 
D/REPLACEMENT_TEST(18563): Character LUT : 1840 ms 
D/REPLACEMENT_TEST(18563): Java NORMALIZER : 2416 ms 

• ですたくさん。
• 私はREGEXESのスピードに関する私の前提について完全に間違っていたことを知っています。devconsoleはノーマライザーの正規表現よりも優れています。
• REGEXESがどれほど遅いかは驚くべきことです。マグニチュードの差は私を本当に驚かせます。私はJava上でそれらを避けようとします。
• ルックアップテーブルは、最も短いオプションです。ノーマライザを使用しているので、私はいくつかの文字を手で置き換える必要があります（スペースを "_"に置き換えて）、小文字に変換してください。

このテストは、Samsung Galaxy Tab v1 10.1で行われました。

テストケースのソースコードが添付されています。

public class Misc { 

    /* Test 2 (@WCChargin's Regex compilation) initialization */ 

static Map<Pattern, String> patterns = new HashMap<Pattern, String>(); 

static { 
     patterns.put(Pattern.compile("[ÁÀÂÄáàäaàáâãäå]") ,"a"); 
     patterns.put(Pattern.compile("æ"),"ae"); 
     patterns.put(Pattern.compile("çÇ"),"c"); 
     patterns.put(Pattern.compile("[ÈÉÊËèéêë]"),"e"); 
     patterns.put(Pattern.compile("[ìíîïÍÌÎÏ]"),"i"); 
     patterns.put(Pattern.compile("ñÑ"),"n");        
     patterns.put(Pattern.compile("[ÓÓÖÔòóôõö]"),"o"); 
     patterns.put(Pattern.compile("œ"),"oe"); 
     patterns.put(Pattern.compile("[ÙÚÛÜùúûü]"), "u"); 
     patterns.put(Pattern.compile("[ýÿ]"),"y"); 
     patterns.put(Pattern.compile("[^a-z A-Z 0-9 \\_ \\+]"),""); 
     patterns.put(Pattern.compile(" "),"_"); 
} 

    /* Test 3 (@devconsole's Lookup table) initialization */ 
static SparseArray<String> homeBrewPatterns=new SparseArray<String>(); 
/** helper function to fill the map where many different chars map to the same replacement */ 
static void fillMap(String chars, String replacement) { for (int i=0,len=chars.length(); i<len; i++) homeBrewPatterns.put(chars.charAt(i), replacement); } 
static { 
    // fill the sparsearray map with all possible substitutions: Any char code gets its equivalent, ie, ä->a. a->a. A->a 
    // this also does the toLowerCase automatically. If a char is not in the list, it is forbidden and we skip it. 
    fillMap("ÁÀÂÄáàäaàáâãäå","a"); 
    fillMap("æ","ae"); 
    fillMap("çÇ","c"); 
    fillMap("ÈÉÊËèéêë","e"); 
    fillMap("ìíîïÍÌÎÏ","i"); 
    fillMap("ñÑ","n"); 
    fillMap("ÓÓÖÔòóôõö","o"); 
    fillMap("œ","oe"); 
    fillMap("ÙÚÛÜùúûü","u"); 
    fillMap("ýÿ","y"); 
    fillMap(" ","_"); 
    for (char c='a'; c<='z'; c++) fillMap(""+c,""+c); // fill standard ASCII lowercase -> same letter 
    for (char c='A'; c<='Z'; c++) fillMap(""+c,(""+c).toLowerCase()); // fill standard ASCII uppercase -> uppercase 
    for (char c='0'; c<='9'; c++) fillMap(""+c,""+c); // fill numbers 
} 

    /** FUNCTION TO TEST #1: Original function, no pattern compilation */ 
public static String makeValidPathName(String rawString) { 
    if (rawString==null) return null; 
    rawString = rawString.replaceAll("[ÁÀÂÄáàäaàáâãäå]","a"); 
    rawString = rawString.replaceAll("æ","ae"); 
    rawString = rawString.replaceAll("çÇ","c"); 
    rawString = rawString.replaceAll("[ÈÉÊËèéêë]","e"); 
    rawString = rawString.replaceAll("[ìíîïÍÌÎÏ]","i"); 
    rawString = rawString.replaceAll("ñÑ","n");        
    rawString = rawString.replaceAll("[ÓÓÖÔòóôõö]","o"); 
    rawString = rawString.replaceAll("œ","oe"); 
    rawString = rawString.replaceAll("[ÙÚÛÜùúûü]", "u"); 
    rawString = rawString.replaceAll("[ýÿ]","y"); 
    rawString = rawString.replaceAll("[^a-z A-Z 0-9 \\_ \\+]",""); 
    rawString = rawString.replaceAll(" ","_"); 
    return rawString.toLowerCase(); 
} 
/** FUNCTION TO TEST #2: @WCChargin's suggestion: Compile patterns then iterate a map */ 
public static String makeValidPathName_compiled(String rawString) { 
    for (Map.Entry<Pattern, String> e : patterns.entrySet()) { 
     rawString=e.getKey().matcher(rawString).replaceAll(e.getValue()); 
    } 
    return rawString.toLowerCase(); 
} 

    /** FUNCTION TO TEST #3: @devconsole's suggestion: Create a LUT with all equivalences then append to a stringbuilder */ 
public static String makeValidPathName_lut(String rawString) { 
    StringBuilder purified=new StringBuilder(rawString.length()); // to avoid resizing 
    String aux; // to avoid creating objects inside the for 
    for (int i=0, len=rawString.length(); i<len; i++) { 
     aux=homeBrewPatterns.get(rawString.charAt(i)); 
     if (aux!=null) purified.append(aux); 
    } 
    return purified.toString(); 
} 

    /** FUNCTION TO TEST #4: @Erik Pragt's suggestion on the use of a Normalizer */ 
public static String makeValidPathName_normalizer(String rawString) { 
     return rawString == null ? null 
      : Normalizer.normalize(rawString, Form.NFD) 
       .replaceAll("\\p{InCombiningDiacriticalMarks}+", ""); 
} 

    /** Test Runner as a Runnable, just do a Handler.post() to run it */ 

public static Runnable msStringReplacementTest=new Runnable() { 

    public void run() { 


    String XTAG="REPLACEMENT_TEST"; 

    Log.d(XTAG, "*** Running Tests"); 

    int ITERATIONS=1000; 

    String[] holder=new String[4]; 

      /* http://www.adhesiontext.com/ to generate dummy long text ... its late n im tired :) */ 

    String tester="e arte nací valse ojales i demediada cesé entrañan domó reo ere fiaréis cinesiterapia fina pronto mensuraré la desatufases adulantes toree fusca ramiro hez apolíneo insalvable atas no enorme mí ojo trola chao fas eh borda no consignataria uno ges no arenque ahuyento y daca pío veló tenle baúl ve birria filo rho fui tañe mean taz raicita alimentarías ano defunciones u reabráis repase apreciaran cantorales ungidas naftalina ex guió abomba o escribimos consultarás des usó saudí mercó yod aborrecieses guiri lupia ña adosado jeringara fe cabalgadura tú descasar diseñe amar limarme escobero latamente e oreó lujuria niñez fabularios da inviernen vejé estañarán dictará sil mírales emoción zar claudiquéis ó e ti ñ veintén dañen ríase esmeraras acató noté as mancharlos avisen chocarnos divertidas y relata nuera usé fié élitro baba upa cu enhornan da toa hechizase genesíacos sol fija aplicó gafa pi enes fin asé deal rolar recurran cacen ha id pis pisó democristiano oes eras lañó ch pino fijad ñ quita hondazos ñ determinad vid corearan corrompimiento pamema meso fofas ocio eco amagados pian bañarla balan cuatrimestrales pijojo desmandara merecedor nu asimiladores denunciándote jada ñudos por descifraseis oré pelote ro botó tu sí mejorado compatibilizaciones enyerba oyeses atinado papa borbón pe dé ñora semis prosada luces leí aconteciesen doy colmará o ve te modismos virola garbillen apostabas abstenido ha bajá le osar cima ají adormecéis ñu mohecí orden abrogándote dan acanilladas uta emú ha emporcara manila arribeña hollejo ver puntead ijadeáis chalanesca pechugón silbo arabescos e i o arenar oxidas palear ce oca enmaderen niñez acude topó aguanieves i aconsejaseis lago él roía grafito ceñir jopo nitritos mofe botáis nato compresores ñu asilo amerizan allanándola cuela ó han ice puya alta lío son de sebo antieconómicas alá aceza latitud faca lavé colocándolos concebirlo miserea ñus gro mearé enchivarse"; 

    long time0=System.currentTimeMillis(); 
    for (int i=0; i<ITERATIONS; i++) holder[0]=makeValidPathName(tester); // store in an array to avoid possible JIT optimizations 
    long elapsed0=System.currentTimeMillis()-time0; 

    Log.d(XTAG, "Original REGEX : "+elapsed0+" ms"); 

    long time1=System.currentTimeMillis(); 
    for (int i=0; i<ITERATIONS; i++) holder[1]=makeValidPathName_compiled(tester); // store in an array to avoid possible JIT optimizations 
    long elapsed1=System.currentTimeMillis()-time1; 

    Log.d(XTAG, "Compiled REGEX : "+elapsed1+" ms"); 

    long time2=System.currentTimeMillis(); 
    for (int i=0; i<ITERATIONS; i++) holder[2]=makeValidPathName_lut(tester); // store in an array to avoid possible JIT optimizations 
    long elapsed2=System.currentTimeMillis()-time2; 

    Log.d(XTAG, "Character LUT : "+elapsed2+" ms"); 

    long time3=System.currentTimeMillis(); 
    for (int i=0; i<ITERATIONS; i++) holder[3]=makeValidPathName_normalizer(tester); // store in an array to avoid possible JIT optimizations 
    long elapsed3=System.currentTimeMillis()-time3; 

    Log.d(XTAG, "Java NORMALIZER : "+elapsed3+" ms"); 

    Log.d(XTAG, "Output 0: "+holder[0]); 
    Log.d(XTAG, "Output 1: "+holder[1]); 
    Log.d(XTAG, "Output 2: "+holder[2]); 
    Log.d(XTAG, "Output 3: "+holder[3]); 
    } 
}; 

Guysは、私はstackoverflowの愛する:)ご提案いただき、誠にありがとうござい:)

Answer 1

そのREPLACに文字をマップする静的Map<Character,String>を構築「a」から「a」、「a」から「a」などへのマップ「Á」である。また、「a」を「a」などにマップする1対1の対応関係も含む。多くの場合、数百のエントリを持つ地図が表示されます。

入力文字列の文字を繰り返して、静的マップ内の置換文字列を探します。地図に項目が含まれていない場合は文字をスキップし、そうでなければStringBuilderに置換を追加します。

Answer 2

あなたがしようとすることができますどのような、代わりに正規表現を使用しての、Normalizerを使用することです。その情報はhereです。そのページから、

：

import java.text.Normalizer; 
import java.text.Normalizer.Form; 

// ... 

public static String removeAccents(String text) { 
    return text == null ? null 
     : Normalizer.normalize(text, Form.NFD) 
      .replaceAll("\\p{InCombiningDiacriticalMarks}+", ""); 
} 

それはすべてのニーズを解決していませんが、それは文字のかなり広範な範囲で動作します。しかし、どちらのソリューションを比較するにしても、パフォーマンス測定を行うことをお勧めします。正規表現の解決法を実際に使いたいのであれば、最初にいくつかの静的なパターンを作成し、その後にMatchersを使用してみてください。そのため、一度パターンを作成するオーバーヘッドが発生します。

Answer 3

あなたは正規表現を使用する必要がある場合、あなたはあなたのパターンをプリコンパイルすることができます：forループで

Map<Pattern, String> patterns = new HashMap<Pattern, String>(); 
{ // initializer block (you could do this in constructor also) 
    patterns.put(Pattern.compile("[ÁÀÂÄáàäaàáâãäå]") ,"a"); 
    rawString = rawString.replaceAll("æ","ae"); 
    // etc. 
} 

// later... 
for (Map.Entry<Pattern, String> e : patterns) { 
    rawString = e.getValue().matcher(rawString).replaceAll(e.getKey()); 
} 

ラインが鍵となります。

• e.getValue()が
• .matcher(rawString)は、与えられた文字列（生の文字列）
• .replaceAll作品への正規表現のインスタンスを一致させるために、パターンをMatcherオブジェクトを取得し、キーマップからパターンを取得します。ここでは解剖ですただString方法（私は実際に、Stringがこれを使用すると信じて）
• e.getKey()がキーマップから交換する値を取得するよう

さらに読書のため

---

リンク：

• Pattern
• Matcher及びその方法replaceAll
• Map.Entry