java - ¸¸µé±â - ¹®ÀÚ¿À» °Ë»öÇÏ´Â È¿À²ÀûÀÎ ¹æ¹ý
java html ¸¸µé±â (10)
Fast Fourier Transforms¸¦ »ç¿ëÇÏ¿© ¸Å¿ì ºü¸¥ ¼Ö·ç¼ÇÀ» ±¸ÇöÇÒ ¼ö ÀÖ½À´Ï´Ù. Á¦´ë·Î ±¸ÇöµÇ¸é O (nlog (m))ÀÇ ¹®ÀÚ¿ ÀÏÄ¡¸¦ ¼öÇà ÇÒ ¼ö ÀÖ½À´Ï´Ù. ¿©±â¼ nÀº ´õ ±ä ¹®ÀÚ¿ÀÇ ±æÀÌÀÌ°í, mÀº ªÀº ¹®ÀÚ¿ÀÇ ±æÀÌÀÔ´Ï´Ù. ¿¹¸¦ µé¾î, ±æÀÌ°¡ m ÀÎ ½ºÆ®¸² ÀÔ·ÂÀ»¹Þ´Â Áï½Ã FFT¸¦ ¼öÇà ÇÒ ¼ö ÀÖ°í, ÀÏÄ¡ÇÏ´Â °æ¿ì ¸®ÅÏ ÇÒ ¼ö ÀÖÀ¸¸ç, ÀÏÄ¡ÇÏÁö ¾ÊÀ¸¸é ½ºÆ®¸² ÀÔ·ÂÀÇ Ã¹ ¹ø° ¹®ÀÚ¸¦ ¹ö¸®°í ´ë±â »õ·Î¿î ij¸¯ÅÍ°¡ ½ºÆ®¸²À» ÅëÇØ ³ªÅ¸³ª°í FFT¸¦ ´Ù½Ã ¼öÇàÇϽʽÿÀ.
ƯÁ¤ ¹®ÀÚ¿À» °Ë»çÇÏ°í ½ÍÀº ÅؽºÆ® ½ºÆ®¸² (¶Ç´Â JavaÀÇ Reader)ÀÌ ÀÖ´Ù°í °¡Á¤ ÇØ º¾½Ã´Ù. ÅؽºÆ®ÀÇ ½ºÆ®¸²ÀÌ ¸Å¿ì Ŭ ¼ö ÀÖÀ¸¹Ç·Î °Ë»ö ¹®ÀÚ¿ÀÌ ¹ß°ßµÇ¸é true¸¦ ¹ÝȯÇÏ°í Àüü ÀÔ·ÂÀ» ¸Þ¸ð¸®¿¡ ÀúÀåÇÏ´Â °ÍÀ» ÇÇÇÏ·Á°íÇÕ´Ï´Ù.
¼øÁøÇÏ°Ô, ³ª´Â ÀÚ¹Ù¿¡¼ ´ÙÀ½°ú °°ÀÌÇÏ·Á°í ½Ãµµ ÇÒ ¼öÀÖ´Ù.
public boolean streamContainsString(Reader reader, String searchString) throws IOException {
char[] buffer = new char[1024];
int numCharsRead;
while((numCharsRead = reader.read(buffer)) > 0) {
if ((new String(buffer, 0, numCharsRead)).indexOf(searchString) >= 0)
return true;
}
return false;
}
¹°·Ð ÀÌ°ÍÀº 1k ¹öÆÛÀÇ °æ°è¿¡¼ ¹ß»ýÇϸé ÁÖ¾îÁø °Ë»ö ¹®ÀÚ¿À» ŽÁöÇÏÁö ¸øÇÕ´Ï´Ù :
°Ë»ö ÅؽºÆ® : "stackoverflow"
½ºÆ®¸² ¹öÆÛ 1 : "abc ......... stack"
½ºÆ®¸² ¹öÆÛ 2 : "¿À¹ö Ç÷οì ....... xyz"
ÀÌ Äڵ带 ¼öÁ¤ÇÏ¿© ¹öÆÛ °æ°è¿¡¼ ÁÖ¾îÁø °Ë»ö ¹®ÀÚ¿À» ã¾ÒÁö¸¸ Àüü ½ºÆ®¸²À» ¸Þ¸ð¸®¿¡·ÎµåÇÏÁö ¾Ê°í ¾î¶»°Ô ãÀ» ¼ö ÀÖ½À´Ï±î?
ÆíÁý : ¹®ÀÚ¿À» °Ë»ö ÇÒ ¶§ ½ºÆ®¸²¿¡¼ Àд Ƚ¼ö ¸¦ ÃÖ¼ÒÈÇÏ°í (³×Æ®¿öÅ© / µð½ºÅ©ÀÇ ´ë±â ½Ã°£À» ÇÇÇϱâ À§ÇØ) ½ºÆ®¸²ÀÇ µ¥ÀÌÅÍ ¾ç¿¡ °ü°è¾øÀÌ ¸Þ¸ð¸® »ç¿ëÀ» ÀÏÁ¤ÇÏ°Ô À¯ÁöÇÏ·Á°í ÇÕ´Ï´Ù. ¹®ÀÚ¿ ¸ÅĪ ¾Ë°í¸®Áò ÀÇ ½ÇÁ¦ È¿À²¼ºÀº ºÎÂ÷ÀûÀÌÁö¸¸ ¾Ë°í¸®Áò ÀǺ¸´Ù È¿À²ÀûÀÎ ¾Ë°í¸®ÁòÀ» »ç¿ëÇÏ´Â ¼Ö·ç¼ÇÀ» ã´Â °ÍÀÌ ÁÁ½À´Ï´Ù.
Reader¸¦ »ç¿ëÇÏÁö ¾Ê´Â´Ù¸é JavaÀÇ NIO API¸¦ »ç¿ëÇÏ¿© È¿À²ÀûÀ¸·Î ÆÄÀÏÀ»·Îµå ÇÒ ¼ö ÀÖ½À´Ï´Ù. ¿¹¸¦ µé¾î (Å×½ºÆ®µÇÁö ¾Ê¾ÒÁö¸¸ ÀÛ¾÷¿¡ °¡±î¿ö ¾ß ÇÔ) :
public boolean streamContainsString(File input, String searchString) throws IOException {
Pattern pattern = Pattern.compile(Pattern.quote(searchString));
FileInputStream fis = new FileInputStream(input);
FileChannel fc = fis.getChannel();
int sz = (int) fc.size();
MappedByteBuffer bb = fc.map(FileChannel.MapMode.READ_ONLY, 0, sz);
CharsetDecoder decoder = Charset.forName("UTF-8").newDecoder();
CharBuffer cb = decoder.decode(bb);
Matcher matcher = pattern.matcher(cb);
return matcher.matches();
}
ÀÌ°ÍÀº ±âº»ÀûÀ¸·Î °Ë»ö ÇÒ ÆÄÀÏÀ» mmap ()ÇÏ°í ij½Ã ¹× ¸Þ¸ð¸® »ç¿ë°ú °ü·ÃÇÏ¿© ¿Ã¹Ù¸¥ ÀÛ¾÷À» ¼öÇàÇϱâ À§ÇØ ¿î¿µ üÁ¦¿¡ ÀÇÁ¸ÇÕ´Ï´Ù. ±×·¯³ª map ()Àº ¾à 10 KiB ¹Ì¸¸ÀÇ ÆÄÀÏ¿¡ ´ëÇØ Å« ¹öÆÛ·Î ÆÄÀÏÀ» Àд °ÍÀÌ ´õ ºñ½Ô´Ï´Ù.
¹öÆÛ »çÀÌÀÇ °æ°è¿¡ ÀÛÀº ¾çÀ» ¹öÆÛ¸µÇؾßÇÑ´Ù°í »ý°¢ÇÕ´Ï´Ù.
¿¹¸¦ µé¾î, ¹öÆÛ Å©±â°¡ 1024ÀÌ°í SearchStringÀÇ ±æÀÌ°¡ 10 ÀÎ °æ¿ì, °¢ 1024 ¹ÙÀÌÆ® ¹öÆÛ¸¦ °Ë»öÇÏ´Â °Í°ú ¸¶Âù°¡Áö·Î µÎ °³ÀÇ ¹öÆÛ »çÀÌ¿¡¼ °¢ 18 ¹ÙÀÌÆ® ÀüȯÀ» °Ë»öÇؾßÇÕ´Ï´Ù (ÀÌÀü ¹öÆÛÀÇ ³¡¿¡¼ 9 ¹ÙÀÌÆ® ´ÙÀ½ ¹öÆÛÀÇ ½ÃÀÛ¿¡¼ 9 ¹ÙÀÌÆ®¿Í ¿¬°áµÊ).
¹öÆÛ¸¦ ¹è¿·Î °¡Áö´Â ´ë½Å ¼øȯ ¹öÆÛ ¸¦ ±¸ÇöÇÏ´Â Ãß»óȸ¦ »ç¿ëÇϽʽÿÀ. À妽º °è»êÀº buf[(next+i) % sizeof(buf)]
°¡ µÉ °ÍÀ̹ǷΠ¹öÆÛ¸¦ ÇÑ ¹ø¿¡ Àý¹Ý ¾¿ ä¿ìµµ·ÏÁÖÀÇÇؾßÇÕ´Ï´Ù. ±×·¯³ª °Ë»ö ¹®ÀÚ¿ÀÌ ¹öÆÛÀÇ Àý¹Ý¿¡ µé¾î°¡¸é ãÀ» ¼ö ÀÖ½À´Ï´Ù.
ºñ½ÁÇÑ ¹®Á¦°¡ »ý°å½À´Ï´Ù. ÁöÁ¤µÈ ¹®ÀÚ¿ (¶Ç´Â ¹ÙÀÌÆ® ¹è¿)±îÁö InputStream¿¡¼ ¹ÙÀÌÆ®¸¦ °Ç³Ê ¶Ý´Ï´Ù. ¿øÇü ¹öÆÛ¸¦ ±â¹ÝÀ¸·ÎÇÏ´Â °£´ÜÇÑ ÄÚµåÀÔ´Ï´Ù. ±×°ÍÀº ¸Å¿ì È¿À²ÀûÀÌÁö´Â ¾ÊÁö¸¸ ³» ¿ä±¸¿¡ ºÎÇÕÇÕ´Ï´Ù.
private static boolean matches(int[] buffer, int offset, byte[] search) {
final int len = buffer.length;
for (int i = 0; i < len; ++i) {
if (search[i] != buffer[(offset + i) % len]) {
return false;
}
}
return true;
}
public static void skipBytes(InputStream stream, byte[] search) throws IOException {
final int[] buffer = new int[search.length];
for (int i = 0; i < search.length; ++i) {
buffer[i] = stream.read();
}
int offset = 0;
while (true) {
if (matches(buffer, offset, search)) {
break;
}
buffer[offset] = stream.read();
offset = (offset + 1) % buffer.length;
}
}
½ºÆ®¸²ÀÇ ¸Å¿ì ºü¸¥ °Ë»öÀº Ujorm ÇÁ·¹ÀÓ ¿öÅ©ÀÇ RingBuffer Ŭ·¡½º¿¡¼ ±¸ÇöµË´Ï´Ù. »ùÇú¸±â :
Reader reader = RingBuffer.createReader("xxx ${abc} ${def} zzz");
String word1 = RingBuffer.findWord(reader, "${", "}");
assertEquals("abc", word1);
String word2 = RingBuffer.findWord(reader, "${", "}");
assertEquals("def", word2);
String word3 = RingBuffer.findWord(reader, "${", "}");
assertEquals("", word3);
SourceForge ¿¡¼ ´ÜÀÏ Å¬·¡½º ±¸ÇöÀ» »ç¿ëÇÒ ¼ö ÀÖ½À´Ï´Ù. ÀÚ¼¼ÇÑ ³»¿ëÀº link ÂüÁ¶ÇϽʽÿÀ.
¿©±â¿¡´Â ¼¼ °¡Áö ÁÁÀº ÇØ°áÃ¥ÀÌ ÀÖ½À´Ï´Ù.
½±°í ÇÕ¸®ÀûÀÎ ¼ÓµµÀÇ ¹«¾ð°¡¸¦ ¿øÇÑ´Ù¸é, ¹öÆÛ°¡¾ø´Â »óÅ¿¡¼ °£´ÜÇÑ ºñ °áÁ¤Àû À¯ÇÑ »óÅ ±â°è¸¦ ±¸ÇöÇϽʽÿÀ. ´ç½ÅÀÇ »óÅ´ ´ç½ÅÀÌ Ã£°íÀÖ´Â ¹®ÀÚ¿¿¡ ´ëÇÑ »öÀÎÀÇ ¸ñ·ÏÀÌ µÉ °ÍÀÌ°í, ´ç½ÅÀÇ ³í¸®´Â ´ÙÀ½°ú °°ÀÌ º¸ÀÏ °ÍÀÔ´Ï´Ù. (ÀÇ»ç ÄÚµå) :
String needle; n = needle.length(); for every input character c do add index 0 to the list for every index i in the list do if c == needle[i] then if i + 1 == n then return true else replace i in the list with i + 1 end else remove i from the list end end end
ÀÌ ¹®ÀÚ¿ÀÌ ÀÖÀ¸¸é ¹öÆÛ¸¦ ÇÊ¿ä·ÎÇÏÁö ¾ÊÀ» °ÍÀÔ´Ï´Ù.
Á¶±Ý ´õ ¸¹Àº ÀÏÀ»ÇÏÁö¸¸ ´õ »¡¸® ¼öÇà ÇÒ ¼öµµ ÀÖ½À´Ï´Ù. »çÀü¿¡ »öÀÎÀÇ ¸ñ·ÏÀÌ ¹«¾ùÀÎÁö ÆľÇÇÏ°í °¢ »öÀÎÀ» ÀÛÀº Á¤¼ö·Î ÇÒ´çÇÏ´Â NFA-DFA º¯È¯À» ¼öÇàÇϽʽÿÀ. (À§Å° ¹é°ú¿¡¼ ¹®ÀÚ¿ °Ë»ö¿¡ ´ëÇØ ÀÐÀº °æ¿ìÀ̸¦ powerset ±¸¹® À̶ó°íÇÕ´Ï´Ù.) ±×·± ´ÙÀ½ ÇϳªÀÇ »óÅ°¡ ÀÖ°í °¢ ¹®ÀÚ°¡ »óÅ¿¡¼ »óÅ·ΠÀüȯµË´Ï´Ù. ¿øÇÏ´Â NFA´Â ºñ °áÁ¤ÀûÀ¸·Î ¹®ÀÚ¸¦ »èÁ¦Çϰųª ÇöÀç ¹®ÀÚ¸¦ »ç¿ëÇÏ·Á°íÇÏ´Â »óÅ°¡ ¼±Çà µÈ ¹®ÀÚ¿¿¡ ´ëÇÑ DFAÀÔ´Ï´Ù. ¸í½Ã Àû ¿À·ù »óŵµ ¿øÇÒ °ÍÀÔ´Ï´Ù.
Á» ´õ ºü¸¥ °ÍÀ» ¿øÇÑ´Ù¸é Àû¾îµµ µÎ ¹èÀÎ Å©±âÀÇ ¹öÆÛ¸¦ ¸¸µé°í »ç¿ëÀÚ Boyer-Moore´Â
needle
·Î »óÅ ¸Ó½ÅÀ» ÄÄÆÄÀÏÇÕ´Ï´Ù. Boyer-Moore´Â ±¸ÇöÇϱⰡ ½±Áö ¾ÊÀ¸¹Ç·Î (Äڵ带 ¿Â¶óÀÎÀ¸·Î ãÀ»Áö¶óµµ) ¹öÆÛ¸¦ ÅëÇØ ¹®ÀÚ¿À» ½½¶óÀ̵åÇؾßÇϹǷΠ¸¹Àº ¹ø°Å ·Î¿òÀÌ ÀÖ½À´Ï´Ù. º¹»çÇÏÁö ¾Ê°í '½½¶óÀ̵å'ÇÒ ¼öÀÖ´Â ¿øÇü ¹öÆÛ¸¦ ¸¸µé°Å³ª ã¾Æ¾ßÇÕ´Ï´Ù. ±×·¸Áö ¾ÊÀ¸¸é Boyer-Moore¿¡¼ ¾òÀ» ¼öÀÖ´Â ¼º´É Çâ»óÀ» µÇµ¹¸± ¼ö ÀÖ½À´Ï´Ù.
ÀÌ ´äº¯Àº Ãʱ⠹öÀüÀÇ Áú¹®¿¡ Àû¿ëµË´Ï´Ù. ¿©±â¿¡¼ StringÀº ¹®ÀÚ¿ÀÌ ÀÏÄ¡ÇÏ´Â °æ¿ì¿¡¸¸ ½ºÆ®¸²À» Àд °ÍÀÌ ¾ú½À´Ï´Ù. ÀÌ ¼Ö·ç¼ÇÀº °íÁ¤ ¸Þ¸ð¸® »ç¿ëÀ» º¸ÀåÇÏ´Â ¿ä±¸ »çÇ×À» ÃæÁ·½ÃÅ°Áö ¾ÊÁö¸¸ÀÌ Áú¹®À» ¹ß°ßÇÏ°í ÇØ´ç Á¦¾à Á¶°Ç¿¡ ±¸¼ÓµÇÁö ¾Ê´Â °æ¿ì °í·ÁÇØ º¼ °¡Ä¡°¡ ÀÖ½À´Ï´Ù.
»ó¼ö ¸Þ¸ð¸® »ç¿ë Á¦¾à Á¶°Ç¿¡ ±¸¼ÓµÇ´Â °æ¿ì Java´Â ¸ðµç À¯ÇüÀÇ ¹è¿À» Èü¿¡ ÀúÀåÇϹǷΠÂüÁ¶¸¦ null·Î ÁöÁ¤ÇÏ¸é ¸Þ¸ð¸®°¡ ÇÒ´çµÇÁö ¾Ê½À´Ï´Ù. ·çÇÁ¿¡¼ ¹è¿°ú °ü·ÃµÈ ¸ðµç ¼Ö·ç¼ÇÀº Èü¿¡¼ ¸Þ¸ð¸®¸¦ ¼ÒºñÇÏ°í GC°¡ ÇÊ¿äÇÒ °ÍÀ̶ó°í »ý°¢ÇÕ´Ï´Ù.
°£´ÜÇÑ ±¸ÇöÀ» À§Çؼ Java 5ÀÇ Scanner ÀÎ InputStreamÀ» ¹Þ¾ÆµéÀÌ°í java.util.regex.Pattern À» »ç¿ëÇÏ¿© ÀÔ·ÂÀ» °Ë»öÇÏ¸é ±¸Çö ¼¼ºÎ »çÇ׿¡ ´ëÇØ °ÆÁ¤ÇÒ ÇÊ¿ä°¡ ¾øÀ» ¼öµµ ÀÖ½À´Ï´Ù.
´ÙÀ½Àº ÀáÀçÀû ÀÎ ±¸Çö ¿¹ÀÔ´Ï´Ù.
public boolean streamContainsString(Reader reader, String searchString)
throws IOException {
Scanner streamScanner = new Scanner(reader);
if (streamScanner.findWithinHorizon(searchString, 0) != null) {
return true;
} else {
return false;
}
}
±×°ÍÀº ¹®ÀÚ¿À» (ÀÏÄ¡ÇÏÁö ¾ÊÀ½) °ÅºÎÇϰųª ¼ö¶ô »óÅ°¡ µÉ ¶§±îÁö ¹®ÀÚ·Î »óÅ ¹®ÀÚ¸¦ º¯°æ, Ãʱ⠻óÅ¿¡¼ ½ÃÀÛÇÏ´Â ¹«¾ð°¡¸¦ À¯ÇÑ »óÅ Automaton¿¡ ´ëÇÑ ÀÛ¾÷ °°¾Æ¿ä ¶§¹®¿¡ Á¤±Ô½Ä »ý°¢ ÇØ¿ä.
³ª´Â ÀÌ°ÍÀÌ ¾Æ¸¶µµ ´ç½ÅÀÌ »ç¿ëÇÒ ¼öÀÖ´Â °¡Àå È¿À²ÀûÀÎ ¸ÅĪ ·ÎÁ÷À̶ó°í »ý°¢Çϸç, Á¤º¸ÀÇ Àб⸦ ±¸¼ºÇÏ´Â ¹æ¹ýÀº ¼º´É Æ©´×À»À§ÇÑ Á¤ÇÕ ·ÎÁ÷°ú ºÐ¸® µÉ ¼ö ÀÖ½À´Ï´Ù.
±×°ÍÀº ¶ÇÇÑ regexes°¡ ÀÛµ¿ÇÏ´Â ¹æ¹ýÀÔ´Ï´Ù.
ÀϺΠ¹®ÀÚ¿ °Ë»ö ¾Ë°í¸®Áò À» »ç¿ëÇÏ¿© ¸Å¿ì Å« ¹®ÀÚ¿ °Ë»ö ¼Óµµ¸¦ ³ôÀÏ ¼ö ÀÖ½À´Ï´Ù
Á¤±Ô Ç¥Çö½ÄÀÌ ¾Æ´Ñ »ó¼ö ºÎºÐ ¹®ÀÚ¿À» ã°í ÀÖ´Ù¸é Boyer-Moore¸¦ ÃßõÇÕ´Ï´Ù. ÀÎÅͳݿ¡´Â ¸¹Àº ¼Ò½º Äڵ尡 ÀÖ½À´Ï´Ù.
¶ÇÇÑ ¹öÆÛ °æ°è¸¦ ³Ê¹« ¼¼°Ô »ý°¢ÇÏÁö ¾ÊÀ¸·Á¸é ¼øȯ ¹öÆÛ¸¦ »ç¿ëÇϽʽÿÀ.
¸¶ÀÌÅ©.